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?)

  • [1] R. Baber, Turán densities of hypercubes, available as arXiv:1201.3587 (2012).
  • [2] Rahil Baber and John Talbot, A solution to the 2/3 conjecture, SIAM J. Discrete Math. 28 (2014), no. 2, 756-766. MR 3209718, https://doi.org/10.1137/130926614
  • [3] Rahil Baber and John Talbot, Hypergraphs do jump, Combin. Probab. Comput. 20 (2011), no. 2, 161-171. MR 2769186, https://doi.org/10.1017/S0963548310000222
  • [4] József Balogh, Ping Hu, Bernard Lidický, and Hong Liu, Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube, European J. Combin. 35 (2014), 75-85. MR 3090487, https://doi.org/10.1016/j.ejc.2013.06.003
  • [5] Béla Bollobás and Oliver Riordan, Sparse graphs: metrics and random models, Random Structures Algorithms 39 (2011), no. 1, 1-38. MR 2839983, https://doi.org/10.1002/rsa.20334
  • [6] Christian Borgs, Jennifer Chayes, and László Lovász, Moments of two-variable functions and the uniqueness of graph limits, Geom. Funct. Anal. 19 (2010), no. 6, 1597-1619. MR 2594615, https://doi.org/10.1007/s00039-010-0044-0
  • [7] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), no. 6, 1801-1851. MR 2455626, https://doi.org/10.1016/j.aim.2008.07.008
  • [8] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs II. Multiway cuts and statistical physics, Ann. of Math. (2) 176 (2012), no. 1, 151-219. MR 2925382, https://doi.org/10.4007/annals.2012.176.1.2
  • [9] Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, Balázs Szegedy, and Katalin Vesztergombi, Graph limits and parameter testing, STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 261-270. MR 2277152, https://doi.org/10.1145/1132516.1132556
  • [10] F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), no. 4, 345-362. MR 1054011, https://doi.org/10.1007/BF02125347
  • [11] David Conlon and Jacob Fox, Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), no. 5, 1191-1256. MR 2989432, https://doi.org/10.1007/s00039-012-0171-x
  • [12] J. W. Cooper, D. Král', and T. Martins, Finitely forcible graph limits are universal, available as arXiv:1701.03846 (2017).
  • [13] Persi Diaconis, Susan Holmes, and Svante Janson, Threshold graph limits and random threshold graphs, Internet Math. 5 (2008), no. 3, 267-320 (2009). MR 2573956
  • [14] Gábor Elek, On limits of finite graphs, Combinatorica 27 (2007), no. 4, 503-507. MR 2359831, https://doi.org/10.1007/s00493-007-2214-8
  • [15] Alan Frieze and Ravi Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), no. 2, 175-220. MR 1723039, https://doi.org/10.1007/s004930050052
  • [16] Roman Glebov, Carlos Hoppen, Tereza Klimošová, Yoshiharu Kohayakawa, Daniel Král', and Hong Liu, Densities in large permutations and parameter testing, European J. Combin. 60 (2017), 89-99. MR 3567538
  • [17] R. Glebov, T. Klimošová, and D. Král', Infinite dimensional finitely forcible graphon, available as arXiv:1404.2743 (2014).
  • [18] R. Glebov, D. Král', and J. Volec, Compactness and finite forcibility of graphons, available as arXiv:1309.6695 (2015).
  • [19] Andrzej Grzesik, On the maximum number of five-cycles in a triangle-free graph, J. Combin. Theory Ser. B 102 (2012), no. 5, 1061-1066. MR 2959390, https://doi.org/10.1016/j.jctb.2012.04.001
  • [20] Hamed Hatami, Jan Hladký, Daniel Král, Serguei Norine, and Alexander Razborov, Non-three-colourable common graphs exist, Combin. Probab. Comput. 21 (2012), no. 5, 734-742. MR 2959863, https://doi.org/10.1017/S0963548312000107
  • [21] Hamed Hatami, Jan Hladký, Daniel Kráľ, Serguei Norine, and Alexander Razborov, On the number of pentagons in triangle-free graphs, J. Combin. Theory Ser. A 120 (2013), no. 3, 722-732. MR 3007147, https://doi.org/10.1016/j.jcta.2012.12.008
  • [22] Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, Balázs Ráth, and Rudini Menezes Sampaio, Limits of permutation sequences, J. Combin. Theory Ser. B 103 (2013), no. 1, 93-113. MR 2995721, https://doi.org/10.1016/j.jctb.2012.09.003
  • [23] C. Hoppen, Y. Kohayakawa, C. G. Moreira, and R. M. Sampaio, Limits of permutation sequences through permutation regularity, available as arXiv:1106.1663 (2011).
  • [24] Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo Moreira, and Rudini Menezes Sampaio, Testing permutation properties through subpermutations, Theoret. Comput. Sci. 412 (2011), no. 29, 3555-3567. MR 2839700, https://doi.org/10.1016/j.tcs.2011.03.002
  • [25] Svante Janson, Poset limits and exchangeable random posets, Combinatorica 31 (2011), no. 5, 529-563. MR 2886098, https://doi.org/10.1007/s00493-011-2591-x
  • [26] Daniel Kráľ, Chun-Hung Liu, Jean-Sébastien Sereni, Peter Whalen, and Zelealem B. Yilma, A new bound for the $ 2/3$ conjecture, Combin. Probab. Comput. 22 (2013), no. 3, 384-393. MR 3053853, https://doi.org/10.1017/S0963548312000612
  • [27] Daniel Kráľ, Lukáš Mach, and Jean-Sébastien Sereni, A new lower bound based on Gromov's method of selecting heavily covered points, Discrete Comput. Geom. 48 (2012), no. 2, 487-498. MR 2946458, https://doi.org/10.1007/s00454-012-9419-3
  • [28] Daniel Král' and Oleg Pikhurko, Quasirandom permutations are characterized by 4-point densities, Geom. Funct. Anal. 23 (2013), no. 2, 570-579. MR 3053756, https://doi.org/10.1007/s00039-013-0216-9
  • [29] László Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR 3012035
  • [30] László Lovász and Vera T. Sós, Generalized quasirandom graphs, J. Combin. Theory Ser. B 98 (2008), no. 1, 146-163. MR 2368030, https://doi.org/10.1016/j.jctb.2007.06.005
  • [31] L. Lovász and B. Szegedy, Finitely forcible graphons, J. Combin. Theory Ser. B 101 (2011), no. 5, 269-301. MR 2802882, https://doi.org/10.1016/j.jctb.2011.03.005
  • [32] László Lovász and Balázs Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), no. 6, 933-957. MR 2274085, https://doi.org/10.1016/j.jctb.2006.05.002
  • [33] László Lovász and Balázs Szegedy, Testing properties of graphs and functions, Israel J. Math. 178 (2010), 113-156. MR 2733066, https://doi.org/10.1007/s11856-010-0060-7
  • [34] Oleg Pikhurko and Alexander Razborov, Asymptotic structure of graphs with the minimum number of triangles, Combin. Probab. Comput. 26 (2017), no. 1, 138-160. MR 3579594, https://doi.org/10.1017/S0963548316000110
  • [35] Oleg Pikhurko and Emil R. Vaughan, Minimum number of $ k$-cliques in graphs with bounded independence number, Combin. Probab. Comput. 22 (2013), no. 6, 910-934. MR 3111549, https://doi.org/10.1017/S0963548313000357
  • [36] Alexander A. Razborov, Flag algebras, J. Symbolic Logic 72 (2007), no. 4, 1239-1282. MR 2371204, https://doi.org/10.2178/jsl/1203350785
  • [37] Alexander A. Razborov, On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J. Discrete Math. 24 (2010), no. 3, 946-963. MR 2680226, https://doi.org/10.1137/090747476
  • [38] Alexander A. Razborov, On the minimal density of triangles in graphs, Combin. Probab. Comput. 17 (2008), no. 4, 603-618. MR 2433944, https://doi.org/10.1017/S0963548308009085
  • [39] Vojtěch Rödl, On universality of graphs with uniformly distributed edges, Discrete Math. 59 (1986), no. 1-2, 125-134. MR 837962, https://doi.org/10.1016/0012-365X(86)90076-2
  • [40] Andrew Thomason, Pseudorandom graphs, Random graphs '85 (Poznań, 1985) North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam, 1987, pp. 307-331. MR 930498
  • [41] Andrew Thomason, Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in combinatorics 1987 (New Cross, 1987) London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 173-195. MR 905280

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