Publication details

Weak regularity and finitely forcible graph limits


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

Year of publication 2018
Type Article in Periodical
Magazine / Source Transactions of the American Mathematical Society
Keywords weak regularity; finitely forcible graph limits
Description 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.

You are running an old browser version. We recommend updating your browser to its latest version.

More info