An algorithmic hypergraph regularity lemma. Issue 2 (7th December 2017)

• Record Type: Journal Article
• Authors: Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias
• Is Part Of: Random structures & algorithms. Volume 52:Issue 2(2018)
• Page Start: 301
• Page End: 353
• Publication Date: 2017-12-07
• Subjects: hypergraph regularity lemma -- algorithm; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20739
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended to k ‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs.