Weak regularity and finitely forcible graph limits

DOI10.1016/J.ENDM.2015.06.021zbMATH Open1346.05241DBLPjournals/endm/CooperKKN15arXiv1507.00067OpenAlexW2964351203WikidataQ57601343 ScholiaQ57601343MaRDI QIDQ322209FDOQ322209

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

Publication date: 14 October 2016

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}^{*}varepsilo{n}^{-2}}$. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.

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

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)

Cites Work

• Title not available (Why is that?)
• Moments of two-variable functions and the uniqueness of graph limits
• Quick approximation to matrices and applications
• Szemerédi's lemma for the analyst
• Bounds for graph regularity and removal lemmas
• Finitely forcible graphons
• Compactness and finite forcibility of graphons
• Infinite‐dimensional finitely forcible graphon

Cited In (3)

• Hypergraph limits: A regularity approach
• Weak regularity and finitely forcible graph limits
• Extremal graph theory and finite forcibility

Recommendations

• Finitely forcible graph limits are universal 👍 👎
• Extremal graph theory and finite forcibility 👍 👎
• Finitely forcible graphons 👍 👎
• Compactness and finite forcibility of graphons 👍 👎
• Hypergraph limits: A regularity approach 👍 👎
• Weak regularity and finitely forcible graph limits 👍 👎
• Finitely forcible graphons with an almost arbitrary structure 👍 👎
• On limits of finite graphs 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)