Infinite dimensional finitely forcible graphon
arXiv:1404.2743 · doi:10.1112/plms.12203
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.
References in corpus (9)
- On the Number of Pentagons in Triangle-Free Graphs
- Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
- Non-three-colorable common graphs exist
- Asymptotic Structure of Graphs with the Minimum Number of Triangles
- A new lower bound based on Gromov's method of selecting heavily covered points
- Limits of permutation sequences through permutation regularity
- Counting flags in triangle-free digraphs
- On limits of finite graphs
- Turán densities of hypercubes