Infinite‐dimensional finitely forcible graphon. Issue 4 (9th October 2018)

• Record Type: Journal Article
• Authors: Glebov, Roman; Klimošová, Tereza; Král', Daniel
• Is Part Of: Proceedings of the London Mathematical Society. Volume 118:Issue 4(2019)
• Page Start: 826
• Page End: 856
• Publication Date: 2018-10-09
• Subjects: 05C35 -- 05C80 (primary); Mathematics -- Periodicals; Mathematics; Periodicals; 510
• DOI: 10.1112/plms.12203
• Languages: English
• ISSNs: 0024-6115

Abstract

Abstract: Graphons are analytic objects associated with convergent sequences of dense graphs. Finitely forcible graphons, that is, 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. Lovász 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 ε ‐regular partition. We disprove the conjecture by constructing a finitely forcible graphon with the space of typical vertices that has infinite dimension.