Infinite-dimensional finitely forcible graphon

DOI10.1112/PLMS.12203MaRDI QIDQ5741849zbMATH OpenOpenAlexWikidataFDO

Authors Roman Glebov, Tereza Klimošová, Daniel Král'

Publication date 15 May 2019

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.2743, http://wrap.warwick.ac.uk/108752/7/WRAP-infinite-dimensional-finitely-forcible-graphon-Kral-2018.pdf

zbMATH Keywords

extremal graphgraph limit

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Graphons are analytic objects associated with convergent sequences of dense graphs. Finitely forcible graphons, i.e., those determined by finitely many subgraph densities, are of particular interest because of their relation to various problems in extremal combinatorics and theoretical computer science. Lovasz and Szegedy conjectured that the topological space of typical vertices of a finitely forcible graphon always has finite dimension, which would have implications on the minimum number of parts in its weak eps-regular partition. We disprove the conjecture by constructing a finitely forcible graphon with the space of typical vertices that has infinite dimension.

Recommendations

• Compactness and finite forcibility of graphons
• Finitely forcible graphons with an almost arbitrary structure
• Weak regularity and finitely forcible graph limits
• Weak regularity and finitely forcible graph limits
• Finitely forcible graphons

Cited in

(8)

• Finitely forcible graph limits are universal
• Extremal graph theory and finite forcibility
• Infinite graphical Frobenius representations
• Finitely forcible graphons
• Compactness and finite forcibility of graphons
• Weak regularity and finitely forcible graph limits
• Finitely forcible graphons and permutons
• Finitely forcible graphons with an almost arbitrary structure

This page was built for publication: Infinite-dimensional finitely forcible graphon

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