Název:	Weak regularity and finitely forcible graph limits
Autoři:	Cooper, Jacob W. Kaiser, Tomáš Král', Daniel Noel, Jonathan A.
Citace zdrojového dokumentu:	COOPER, J. W., KAISER, T., KRÁL', D., NOEL, J. A. Weak regularity and finitely forcible graph limits. Transactions of the American mathematical society, 2018, roč. 370, č. 6, s. 3833-3864. ISSN 0002-9947.
Datum vydání:	2018
Nakladatel:	American Mathematical Society
Typ dokumentu:	článek article
URI:	2-s2.0-85044404667 http://hdl.handle.net/11025/35700
ISSN:	0002-9947
Klíčová slova v dalším jazyce:	graph limit;graphon;weak regularity;forcibility
Abstrakt v dalším jazyce:	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 subgraph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak ε-regular partition with the number of parts bounded by a polynomial in ε^{−1}. We construct a finitely forcible graphon W such that the number of parts in any weak ε-regular partition of W is at least exponential in ε^{−2}/2^{5 log* ε^{-2}}. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.
Práva:	Plný text není přístupný. © American Mathematical Society
Vyskytuje se v kolekcích:	Články / Articles (NTIS) Články / Articles (KMA) OBD

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.