Publication details

Finitely Forcible Graphons with an Almost Arbitrary Structure


KRÁĽ Daniel LOVASZ Laszlo M. NOEL Jonathan A. SOSNOVEC Jakub

Year of publication 2020
Type Article in Periodical
Magazine / Source Discrete Analysis
MU Faculty or unit

Faculty of Informatics

Keywords graph limits; finite forcibility
Description 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 strengthen this result by showing for every epsilon > 0 that any graphon spans a 1- epsilon proportion of a finitely forcible graphon.

You are running an old browser version. We recommend updating your browser to its latest version.

More info