Informace o publikaci
Weak regularity and finitely forcible graph limits
| Autoři | |
|---|---|
| Rok publikování | 2018 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Transactions of the American Mathematical Society |
| Citace | |
| www | http://dx.doi.org/10.1090/tran/7066 |
| Doi | http://dx.doi.org/10.1090/tran/7066 |
| 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. |