Publication details
Finitely Forcible Graphons with an Almost Arbitrary Structure
| Authors | |
|---|---|
| Year of publication | 2020 |
| Type | Article in Periodical |
| Magazine / Source | Discrete Analysis |
| MU Faculty or unit | |
| Citation | |
| Web | http://dx.doi.org/10.19086/da.12058 |
| Doi | http://dx.doi.org/10.19086/da.12058 |
| 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. |