A Simple Regularization of Hypergraphs

2006/12/28 by Yoshiyasu Ishigami, Ishigami, Yoshiyasu · 1 citation
Computer Science · Mathematics · #05C65 #05D40 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.math/0612838

openalex publication_date 2006/12/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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).

Citations

• Removal lemma for infinitely-many forbidden hypergraphs and property testing
• On Some Sequences of Integers
• On a Problem of Formal Logic
• On Certain Sets of Integers
• Hypergraph regularity and the multidimensional Szemerédi theorem
• The primes contain arbitrarily long arithmetic progressions

Cited by

• A hypergraph blow-up lemma

Related

• A simple regularization of graphs
• Hypergraph regularity and random sampling
• Szemerédi's regularity lemma revisited
• Regularity inheritance in hypergraphs
• A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal lemma