Hypergraph limits: A regularity approach

DOI10.1002/RSA.20537MaRDI QIDQ3192379zbMATH OpenOpenAlexFDO

Authors Yufei Zhao

Publication date 12 October 2015

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.1634

zbMATH Keywords

exchangeable random arraysgraph limithypergraph limithypergraph regularity

Mathematics Subject Classification ID

Hypergraphs (05C65)

Abstract: A sequence of $k$-uniform hypergraphs $H_1,H_2,dots$ is convergent if the sequence of homomorphism densities $t(F,H_1),t(F,H_2),dots$ converges for every $k$-uniform hypergraph $F$. For graphs, Lov'asz and Szegedy showed that every convergent sequence has a limit in the form of a symmetric measurable function $Wcolon[0,1{]}^{2}o[0,1]$. For hypergraphs, analogous limits $Wcolon[0,1{]}^{2^k-2}o[0,1]$ were constructed by Elek and Szegedy using ultraproducts. These limits had also been studied earlier by Hoover, Aldous, and Kallenberg in the setting of exchangeable random arrays. In this paper, we give a new proof and construction of hypergraph limits. Our approach is inspired by the original approach of Lov'asz and Szegedy, with the key ingredient being a weak Frieze-Kannan type regularity lemma.

Recommendations

• A tight bound for hypergraph regularity
• Hyperfinite graph limits
• On characterizing hypergraph regularity
• scientific article; zbMATH DE number 5130822
• The hypergraph regularity method and its applications
• On limits of finite graphs
• An Algorithmic Regularity Lemma for Hypergraphs
• Weak regularity and finitely forcible graph limits
• Weak regularity and finitely forcible graph limits

Cites work

• A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
• A measure-theoretic approach to the theory of dense hypergraphs
• A variant of the hypergraph removal lemma
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Exchangeability and continuum limits of discrete random structures
• Graph limits and exchangeable random graphs
• Hypergraph regularity and the multidimensional Szemerédi theorem
• Large networks and graph limits
• Limits of dense graph sequences
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• Probability with Martingales
• Quick approximation to matrices and applications
• Representations for partially exchangeable arrays of random variables
• Symmetries on random arrays and set-indexed processes
• Szemerédi's lemma for the analyst
• The counting lemma for regular k‐uniform hypergraphs

Cited in

(21)

• Limits of iterated \(H\)-line graphs
• Limits of structures and the example of tree semi-lattices
• Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
• A limit law of almost l-partite graphs
• Weak regularity and finitely forcible graph limits
• A measure-theoretic approach to the theory of dense hypergraphs
• Weak regularity and finitely forcible graph limits
• scientific article; zbMATH DE number 780943 (Why is no real title available?)
• Triforce and corners
• Random Simplicial Complexes: Models and Phenomena
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Nonparametric modeling of higher-order interactions via hypergraphons
• On the limit of the positive -degree Turán problem
• Hypergraphon mean field games
• Ordered and colored subgraph density problems
• Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
• Vlasov equations on directed hypergraph measures
• Ordered graph limits and their applications
• Pixelating relations and functions without adding substructures
• Hyperfinite graph limits
• On exchangeable random variables and the statistics of large graphs and hypergraphs

This page was built for publication: Hypergraph limits: A regularity approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192379)