A measure-theoretic approach to the theory of dense hypergraphs

By Gábor Elek, Balázs Szegedy. 2008

124 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/874cd214b4ffe1a50cd52efd8397edd1937b53cc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Surveys in Combinatorics 2011: Hypergraph Turán problems (2011, background): “Further generalisations of the theory from graphs to hypergraphs given in [47] are the equivalence of various definitions of convergence (Theorem 14), and a”
Limits of locally–globally convergent graph sequences (2012, methodology): “An alternative proof of Theorem 3.2 can be based on the ultraproduct method of Elek and Szegedy [17].”
Graphons, cut norm and distance, couplings and rearrangements (2010, background): “The basic idea of graph limits has been generalized to limits of many other finite combinatorial objects such as weighted graphs, directed graphs, multigraphs, bipartite graphs, hypergraphs, posets and permutations, see for example [4, 14, 15, 24, 26, 36, 40, 44, 51, 52].”
ON possible Turán densities (2012, methodology): “In particular, we do not rely on the machinery developed by Elek and Szegedy [13].”