Informace o publikaci

Weak regularity and finitely forcible graph limits


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

Rok publikování 2018
Druh Článek v odborném periodiku
Časopis / Zdroj Transactions of the American Mathematical Society
Klíčová slova weak regularity; finitely forcible graph limits
Popis 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.