Weak regularity and finitely forcible graph limits

COOPER, Jacob; Tomáš KAISER; Daniel KRÁĽ a Jonathan NOEL. Weak regularity and finitely forcible graph limits. Transactions of the American Mathematical Society. American Mathematical Society, 2018, roč. 370, č. 6, s. 3833-3864. ISSN 0002-9947. Dostupné z: https://doi.org/10.1090/tran/7066.

Základní údaje

Originální název

Weak regularity and finitely forcible graph limits

Autoři

COOPER, Jacob; Tomáš KAISER; Daniel KRÁĽ a Jonathan NOEL

Vydání

Transactions of the American Mathematical Society, American Mathematical Society, 2018, 0002-9947

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Spojené státy

Utajení

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

Odkazy

URL

Impakt faktor

Impact factor: 1.318

DOI

https://doi.org/10.1090/tran/7066

UT WoS

000428311400003

EID Scopus

2-s2.0-85044404667

Klíčová slova anglicky

weak regularity; finitely forcible graph limits

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

Graphons are analytic objects representing limits of convergent sequences of graphs. Lovász and Szegedy conjectured that every finitely forcible graphon, i.e., any graphon determined by finitely many graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak epsilon-regular partition with the number of parts bounded by a polynomial in epsilon^-1. We construct a finitely forcible graphon W such that the number of parts in any weak epsilon-regular partition of W is at least exponential in epsilon ^-2/2^(5*logstar epsilon^-2). This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.