%0 Journal Article
%T Weak regularity and finitely forcible graph limits
%A Jacob W. Cooper
%A Tom¨¢£¿ Kaiser
%A Daniel Kr¨¢£¿
%A Jonathan A. Noel
%J Computer Science
%D 2015
%I arXiv
%X Graphons are analytic objects representing limits of convergent sequences of graphs. Lov\'asz and Szegedy conjectured that every finitely forcible graphon, i.e. any graphon determined by finitely many subgraph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak $\varepsilon$-regular partition with the number of parts bounded by a polynomial in $\varepsilon^{-1}$. We construct a finitely forcible graphon $W$ such that the number of parts in any weak $\varepsilon$-regular partition of $W$ is at least exponential in $\varepsilon^{-2}/2^{5\log^*\varepsilon^{-2}}$. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.
%U http://arxiv.org/abs/1507.00067v1