A Simple Regularization of Hypergraphs

Abstract

We give a simple and natural (probabilistic) construction of hypergraph regularization. It is done just by taking a constant-bounded number of random vertex samplings only one time (thus, iteration-free). It is independent from the definition of quasi-randomness and yields a new elementary proof of a strong hypergraph regularity lemma. Consequently, as an example of its applications, we have a new self-contained proof of Szemerédi's classic theorem on arithmetic progressions (1975) as well as its multidimensional extension by Furstenberg-Katznelson (1978).

16 pages

References in corpus (3)

• Hypergraph regularity and the multidimensional Szemerédi theorem
• Linear Ramsey numbers for bounded-degree hypergraphs
• Removal lemma for infinitely-many forbidden hypergraphs and property testing

Cited by in corpus (6)

• On the testability and repair of hereditary hypergraph properties
• Linear Ramsey numbers for bounded-degree hypergraphs
• The number of hypergraphs and colored Hypergraphs with hereditary properties
• Removal lemma for infinitely-many forbidden hypergraphs and property testing
• A simple regularization of graphs
• The Symmetry Preserving Removal Lemma