Weak regularity and finitely forcible graph limits

DOI10.1016/J.ENDM.2015.06.021MaRDI QIDQ322209zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Jacob W. Cooper, Tomáš Kaiser, Daniel Král', Jonathan A. Noel

Publication date 14 October 2016

Full work available at URL https://arxiv.org/abs/1507.00067, http://wrap.warwick.ac.uk/81519/7/WRAP-forcible-graph-limits-Kral-2018.pdf

zbMATH Keywords

graph limitsfinitely forcible graphonsweak regularity

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75)

Abstract: Graphons are analytic objects representing limits of convergent sequences of graphs. Lov'asz and Szegedy conjectured that every finitely forcible graphon, i.e. any graphon determined by finitely many graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak $varepsilon$-regular partition with the number of parts bounded by a polynomial in $varepsilo{n}^{-1}$. We construct a finitely forcible graphon $W$ such that the number of parts in any weak $varepsilon$-regular partition of $W$ is at least exponential in $varepsilo{n}^{-2}/2^{5lo{g}^{\ast }varepsilo{n}^{-2}}$. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.

Recommendations

• Weak regularity and finitely forcible graph limits
• Finitely forcible graph limits are universal
• Compactness and finite forcibility of graphons
• Hypergraph limits: A regularity approach
• On limits of finite graphs
• Extremal graph theory and finite forcibility
• Finitely forcible graphons
• Finitely forcible graphons with an almost arbitrary structure
• scientific article; zbMATH DE number 1330009
• Regularity lemmas for graphs

Cites work

• Bounds for graph regularity and removal lemmas
• Compactness and finite forcibility of graphons
• Finitely forcible graphons
• Infinite-dimensional finitely forcible graphon
• Large networks and graph limits
• Moments of two-variable functions and the uniqueness of graph limits
• Quick approximation to matrices and applications
• Szemerédi's lemma for the analyst

Cited in

(7)

• Hypergraph limits: A regularity approach
• Regularity partitions and the topology of graphons
• Weak regularity and finitely forcible graph limits
• Extremal graph theory and finite forcibility
• Infinite-dimensional finitely forcible graphon
• Approximating fractionally isomorphic graphons
• Compactness and finite forcibility of graphons

This page was built for publication: Weak regularity and finitely forcible graph limits

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