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
HTML articles powered by AMS MathViewer

by Jacob W. Cooper, Tomáš Kaiser, Daniel Král’ and Jonathan A. Noel PDF

Trans. Amer. Math. Soc. 370 (2018), 3833-3864 Request permission

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 10.1137/130926614
Rahil Baber and John Talbot, Hypergraphs do jump, Combin. Probab. Comput. 20 (2011), no. 2, 161–171. MR 2769186, DOI 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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, DOI 10.1090/coll/060
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 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 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 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 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 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 10.1017/S0963548313000357
Alexander A. Razborov, Flag algebras, J. Symbolic Logic 72 (2007), no. 4, 1239–1282. MR 2371204, DOI 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 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 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 10.1016/0012-365X(86)90076-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