Title:	Weak regularity and finitely forcible graph limits
Authors:	Cooper, Jacob W. Kaiser, Tomáš Král', Daniel Noel, Jonathan A.
Citation:	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.
Issue Date:	2018
Publisher:	American Mathematical Society
Document type:	článek article
URI:	2-s2.0-85044404667 http://hdl.handle.net/11025/35700
ISSN:	0002-9947
Keywords in different language:	graph limit;graphon;weak regularity;forcibility
Abstract in different language:	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.
Rights:	Plný text není přístupný. © American Mathematical Society
Appears in Collections:	Články / Articles (NTIS) Články / Articles (KMA) OBD

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.