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
URI: 2-s2.0-85044404667
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)

Files in This Item:
File SizeFormat 
S0002-9947-2018-07066-0.pdf449,8 kBAdobe PDFView/Open    Request a copy

Please use this identifier to cite or link to this item: http://hdl.handle.net/11025/35700

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

  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD