Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Weak regularity and finitely forcible graph limits


Authors: Jacob W. Cooper, Tomáš Kaiser, Daniel Král’ and Jonathan A. Noel
Journal: Trans. Amer. Math. Soc. 370 (2018), 3833-3864
MSC (2010): Primary 05C35, 05C80
DOI: https://doi.org/10.1090/tran/7066
Published electronically: February 28, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: 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 $ \varepsilon $-regular partition with the number of parts bounded by a polynomial in $ \varepsilon ^{-1}$. We construct a finitely forcible graphon $ W$ such that the number of parts in any weak $ \varepsilon $-regular partition of $ W$ is at least exponential in $ \varepsilon ^{-2}/2^{5\log ^*\varepsilon ^{-2}}$. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C35, 05C80

Retrieve articles in all journals with MSC (2010): 05C35, 05C80


Additional Information

Jacob W. Cooper
Affiliation: Department of Computer Science, University of Warwick, Coventry CV4 7AL, United Kingdom
Address at time of publication: Department of Mathematics and Statistics, McGill University, Montreal H3A 0B9, Canada
Email: jacob.cooper@mail.mcgill.ca

Tomáš Kaiser
Affiliation: Department of Mathematics, Institute for Theoretical Computer Science (CE-ITI) and the European Centre of Excellence NTIS (New Technologies for the Information Society), University of West Bohemia, Univerzitní 8, 306 14 Plzeň, Czech Republic
Email: kaisert@kma.zcu.cz

Daniel Král’
Affiliation: Mathematics Institute, DIMAP and Department of Computer Science, University of Warwick, Coventry CV4 7AL, United Kingdom
Email: d.kral@warwick.ac.uk

Jonathan A. Noel
Affiliation: Mathematical Institute, University of Oxford, Oxford OX2 6GG, United Kingdom
Address at time of publication: Department of Computer Science and DIMAP, University of Warwick, Coventry CV4 7AL, United Kingdom
Email: j.noel@warwick.ac.uk

DOI: https://doi.org/10.1090/tran/7066
Received by editor(s): July 6, 2015
Received by editor(s) in revised form: July 20, 2016, and August 26, 2016
Published electronically: February 28, 2018
Additional Notes: The work of the first and third authors leading to this invention has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 259385.
The second author was supported by the grant GA14-19503S (Graph coloring and structure) of the Czech Science Foundation.
The work of the third author was also supported by the Engineering and Physical Sciences Research Council Standard Grant number EP/M025365/1.
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society