Weak regularity and finitely forcible graph limits

Cooper, Jacob; Kaiser, Tomáš; Král’, Daniel; Noel, Jonathan

doi:10.1090/tran/7066

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
MathSciNet review: 3811511
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

R. Baber, Turán densities of hypercubes, available as arXiv:1201.3587 (2012).

Rahil Baber and John Talbot, A solution to the 2/3 conjecture, SIAM J. Discrete Math. 28 (2014), no. 2, 756–766. MR 3209718, DOI https://doi.org/10.1137/130926614

Rahil Baber and John Talbot, Hypergraphs do jump, Combin. Probab. Comput. 20 (2011), no. 2, 161–171. MR 2769186, DOI https://doi.org/10.1017/S0963548310000222

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, DOI https://doi.org/10.1016/j.ejc.2013.06.003

Béla Bollobás and Oliver Riordan, Sparse graphs: metrics and random models, Random Structures Algorithms 39 (2011), no. 1, 1–38. MR 2839983, DOI https://doi.org/10.1002/rsa.20334

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, DOI https://doi.org/10.1007/s00039-010-0044-0

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, DOI https://doi.org/10.1016/j.aim.2008.07.008

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, DOI https://doi.org/10.4007/annals.2012.176.1.2

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, DOI https://doi.org/10.1145/1132516.1132556

F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), no. 4, 345–362. MR 1054011, DOI https://doi.org/10.1007/BF02125347

David Conlon and Jacob Fox, Bounds for graph regularity and removal lemmas, Geom. Funct. Anal. 22 (2012), no. 5, 1191–1256. MR 2989432, DOI https://doi.org/10.1007/s00039-012-0171-x

J. W. Cooper, D. Král’, and T. Martins, Finitely forcible graph limits are universal, available as arXiv:1701.03846 (2017).

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

Gábor Elek, On limits of finite graphs, Combinatorica 27 (2007), no. 4, 503–507. MR 2359831, DOI https://doi.org/10.1007/s00493-007-2214-8

Alan Frieze and Ravi Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), no. 2, 175–220. MR 1723039, DOI https://doi.org/10.1007/s004930050052

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, DOI https://doi.org/10.1016/j.ejc.2016.09.006

R. Glebov, T. Klimošová, and D. Král’, Infinite dimensional finitely forcible graphon, available as arXiv:1404.2743 (2014).

R. Glebov, D. Král’, and J. Volec, Compactness and finite forcibility of graphons, available as arXiv:1309.6695 (2015).

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, DOI https://doi.org/10.1016/j.jctb.2012.04.001

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, DOI https://doi.org/10.1017/S0963548312000107

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, DOI https://doi.org/10.1016/j.jcta.2012.12.008

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, DOI https://doi.org/10.1016/j.jctb.2012.09.003

C. Hoppen, Y. Kohayakawa, C. G. Moreira, and R. M. Sampaio, Limits of permutation sequences through permutation regularity, available as arXiv:1106.1663 (2011).

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, DOI https://doi.org/10.1016/j.tcs.2011.03.002

Svante Janson, Poset limits and exchangeable random posets, Combinatorica 31 (2011), no. 5, 529–563. MR 2886098, DOI https://doi.org/10.1007/s00493-011-2591-x

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, DOI https://doi.org/10.1017/S0963548312000612

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, DOI https://doi.org/10.1007/s00454-012-9419-3

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, DOI https://doi.org/10.1007/s00039-013-0216-9

László Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR 3012035

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, DOI https://doi.org/10.1016/j.jctb.2007.06.005

L. Lovász and B. Szegedy, Finitely forcible graphons, J. Combin. Theory Ser. B 101 (2011), no. 5, 269–301. MR 2802882, DOI https://doi.org/10.1016/j.jctb.2011.03.005

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, DOI https://doi.org/10.1016/j.jctb.2006.05.002

László Lovász and Balázs Szegedy, Testing properties of graphs and functions, Israel J. Math. 178 (2010), 113–156. MR 2733066, DOI https://doi.org/10.1007/s11856-010-0060-7

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, DOI https://doi.org/10.1017/S0963548316000110

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, DOI https://doi.org/10.1017/S0963548313000357

Alexander A. Razborov, Flag algebras, J. Symbolic Logic 72 (2007), no. 4, 1239–1282. MR 2371204, DOI https://doi.org/10.2178/jsl/1203350785

Alexander A. Razborov, On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J. Discrete Math. 24 (2010), no. 3, 946–963. MR 2680226, DOI https://doi.org/10.1137/090747476

Alexander A. Razborov, On the minimal density of triangles in graphs, Combin. Probab. Comput. 17 (2008), no. 4, 603–618. MR 2433944, DOI https://doi.org/10.1017/S0963548308009085

Vojtěch Rödl, On universality of graphs with uniformly distributed edges, Discrete Math. 59 (1986), no. 1-2, 125–134. MR 837962, DOI https://doi.org/10.1016/0012-365X%2886%2990076-2

Andrew Thomason, Pseudorandom graphs, Random graphs ’85 (Poznań, 1985) North-Holland Math. Stud., vol. 144, North-Holland, Amsterdam, 1987, pp. 307–331. MR 930498

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