Publication details
Weak regularity and finitely forcible graph limits
| Authors | |
|---|---|
| Year of publication | 2018 |
| Type | Article in Periodical |
| Magazine / Source | Transactions of the American Mathematical Society |
| Citation | |
| Web | http://dx.doi.org/10.1090/tran/7066 |
| Doi | http://dx.doi.org/10.1090/tran/7066 |
| 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. |