Finitely Forcible Graphons with an Almost Arbitrary Structure

KRÁĽ, Daniel; Laszlo M. LOVASZ; Jonathan A. NOEL a Jakub SOSNOVEC. Finitely Forcible Graphons with an Almost Arbitrary Structure. Discrete Analysis. CAMBRIDGE: ALLIANCE DIAMOND OPEN ACCESS JOURNALS, 2020, roč. 2020, č. 9, s. 1-36. ISSN 2397-3129. Dostupné z: https://doi.org/10.19086/da.12058.

Základní údaje

Originální název

Finitely Forcible Graphons with an Almost Arbitrary Structure

Autoři

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

Vydání

Discrete Analysis, CAMBRIDGE, ALLIANCE DIAMOND OPEN ACCESS JOURNALS, 2020, 2397-3129

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Velká Británie a Severní Irsko

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/20:00116815

Organizační jednotka

Fakulta informatiky

DOI

https://doi.org/10.19086/da.12058

UT WoS

000562346400001

EID Scopus

2-s2.0-85117058606

Klíčová slova anglicky

graph limits; finite forcibility

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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.