Informace o publikaci
Finitely Forcible Graphons with an Almost Arbitrary Structure
| Autoři | |
|---|---|
| Rok publikování | 2020 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Discrete Analysis |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://dx.doi.org/10.19086/da.12058 |
| Doi | http://dx.doi.org/10.19086/da.12058 |
| Klíčová slova | graph limits; finite forcibility |
| Popis | 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. |