Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - A measure-theory approach to the theory of dense hypergraphs
AU - Elek, Gábor
AU - Szegedy, Balázs
PY - 2012/10
Y1 - 2012/10
N2 - In this paper we develop a measure-theoretic method to treat problems in hypergraph theory. Our central theorem is a correspondence principle between three objects: an increasing hypergraph sequence, a measurable set in an ultraproduct space and a measurable set in a finite dimensional Lebesgue space. Using this correspondence principle we build up the theory of dense hypergraphs from scratch. Along these lines we give new proofs for the Hypergraph Removal Lemma, the Hypergraph Regularity Lemma, the Counting Lemma and the Testability of Hereditary Hypergraph Properties. We prove various new results including a strengthening of the Regularity Lemma and an Inverse Counting Lemma. We also prove the equivalence of various notions for convergence of hypergraphs and we construct limit objects for such sequences. We prove that the limit objects are unique up to a certain family of measure preserving transformations. As our main tool we study the integral and measure theory on the ultraproduct of finite measure spaces which is interesting on its own right.
AB - In this paper we develop a measure-theoretic method to treat problems in hypergraph theory. Our central theorem is a correspondence principle between three objects: an increasing hypergraph sequence, a measurable set in an ultraproduct space and a measurable set in a finite dimensional Lebesgue space. Using this correspondence principle we build up the theory of dense hypergraphs from scratch. Along these lines we give new proofs for the Hypergraph Removal Lemma, the Hypergraph Regularity Lemma, the Counting Lemma and the Testability of Hereditary Hypergraph Properties. We prove various new results including a strengthening of the Regularity Lemma and an Inverse Counting Lemma. We also prove the equivalence of various notions for convergence of hypergraphs and we construct limit objects for such sequences. We prove that the limit objects are unique up to a certain family of measure preserving transformations. As our main tool we study the integral and measure theory on the ultraproduct of finite measure spaces which is interesting on its own right.
KW - Hypergraphs
KW - Regulatory Iemma
KW - Limit objects
KW - Property testing
U2 - 10.1016/j.aim.2012.06.022
DO - 10.1016/j.aim.2012.06.022
M3 - Journal article
VL - 231
SP - 1731
EP - 1772
JO - Advances in Mathematics
JF - Advances in Mathematics
SN - 0001-8708
IS - 3-4
ER -