A measure-theoretic approach to the theory of dense hypergraphs
From MaRDI portal
Publication:456779
DOI10.1016/J.AIM.2012.06.022zbMATH Open1251.05115arXiv0810.4062OpenAlexW2061886541MaRDI QIDQ456779FDOQ456779
Publication date: 16 October 2012
Published in: Advances in Mathematics (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/0810.4062
Recommendations
- Hypergraph limits: A regularity approach
- A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
- Limits of dense graph sequences
- An analytic approach to sparse hypergraphs: hypergraph removal
- Hypergraph regularity and the multidimensional Szemerédi theorem
Cites Work
- Limits of dense graph sequences
- Moments of two-variable functions and the uniqueness of graph limits
- Regularity Lemma for k-uniform hypergraphs
- The counting lemma for regular k‐uniform hypergraphs
- Generalizations of the removal lemma
- Conversion from Nonstandard to Standard Measure Spaces and Applications in Probability Theory
- Model theory.
- Regular Partitions of Hypergraphs: Regularity Lemmas
- On Homogeneous Measure Algebras
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- A variant of the hypergraph removal lemma
- Testability and repair of hereditary hypergraph properties
- Graph limits and parameter testing
- On exchangeable random variables and the statistics of large graphs and hypergraphs
- Title not available (Why is that?)
- Symmetries on random arrays and set-indexed processes
- A Note on a Question of Erdős and Graham
Cited In (50)
- Triforce and corners
- Semantic limits of dense combinatorial objects
- Multiple recurrence in quasirandom groups
- On replica symmetry of large deviations in random graphs
- On the maximum density of fixed strongly connected subtournaments
- Limits of kernel operators and the spectral regularity lemma
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Natural quasirandomness properties
- Hypergraph limits: A regularity approach
- Finite function spaces and measures on hypergraphs
- The minimum size of 3-graphs without a 4-set spanning no or exactly three edges
- Uniqueness of Banach space valued graphons
- Cut distance identifying graphon parameters over weak* limits
- Density and regularity theorems for semi-algebraic hypergraphs
- Random Simplicial Complexes: Models and Phenomena
- Title not available (Why is that?)
- On possible Turán densities
- Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
- Differential calculus on graphon space
- Two equivalent measures on weighted hypergraphs
- Weighted Quasi-Arithmetic Mean on Two-Dimensional Regions and Their Applications
- An analytic approach to stability
- A problem of Erdős and Sós on 3-graphs
- A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
- A tight bound for hypergraph regularity
- σ-algebras for quasirandom hypergraphs
- Concentration function for pyramid and quantum metric measure space
- Graph limits and hereditary properties
- The inducibility of blow-up graphs
- Arithmetic progressions, different regularity lemmas and removal lemmas
- Poset limits can be totally ordered
- First order convergence of matroids
- Restricted problems in extremal combinatorics
- On the limit of the positive \(\ell\)-degree Turán problem
- Relating the cut distance and the weak* topology for graphons
- On pattern-avoiding permutons
- Regularity and inverse theorems for uniformity norms on compact abelian groups and nilmanifolds
- An uncountable ergodic Roth theorem and applications
- An analytic approach to sparse hypergraphs: hypergraph removal
- Quasi-random graphs and graph limits
- Limits of functions on groups
- Examples in the entropy theory of countable group actions
- Concentration estimates for functions of finite high‐dimensional random arrays
- Structural Properties of Sparse Graphs
- Hyperfinite graph limits
- Convergence and limits of finite trees
- Correcting continuous hypergraphs
- Continuous stable regularity
- Hypergraphon mean field games
- Limits of locally-globally convergent graph sequences
This page was built for publication: A measure-theoretic approach to the theory of dense hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456779)
