Finitely forcible graphons with an almost arbitrary structure

Abstract

Graphons are analytic objects representing convergent sequences of large graphs. A graphon is said to be finitely forcible if it is determined by finitely many subgraph densities, i.e., if the asymptotic structure of graphs represented by such a graphon depends only on finitely many density constraints. Such graphons appear in various scenarios, particularly in extremal combinatorics. Lovasz and Szegedy conjectured that all finitely forcible graphons possess a simple structure. This was disproved in a strong sense by Cooper, Kral and Martins, who showed that any graphon is a subgraphon of a finitely forcible graphon. We strenghten this result by showing for every $\epsilon >0$ that any graphon spans a $1-\epsilon$ proportion of a finitely forcible graphon.

References in corpus (6)

• 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
• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Asymptotic Structure of Graphs with the Minimum Number of Triangles
• Infinite dimensional finitely forcible graphon

Cited by in corpus (1)

• Cut distance identifying graphon parameters over weak* limits