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://dx.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

• Originální 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í
• WWW: URL
• Impakt faktor: Impact factor: 1.318
• Doi: http://dx.doi.org/10.1090/tran/7066
• UT WoS: 000428311400003
• Klíčová slova anglicky: weak regularity; finitely forcible graph limits
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.