Publication details

Infinite-dimensional finitely forcible graphon

Authors

GLEBOV Roman KLIMOŠOVÁ Tereza KRÁĽ Daniel

Year of publication 2019
Type Article in Periodical
Magazine / Source Proceedings of the London mathematical society
MU Faculty or unit

Faculty of Informatics

Citation
Web http://dx.doi.org/10.1112/plms.12203
Doi http://dx.doi.org/10.1112/plms.12203
Keywords Graph limits; large graphs
Description 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. 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 epsilon-regular partition. We disprove the conjecture by constructing a finitely forcible graphon with the space of typical vertices that has infinite dimension.