Semantic limits of dense combinatorial objects

L. N. Coregliano   ; A. A. Razborov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 75 (2020) no. 4, pp. 627-723

Résumé

The theory of limits of discrete combinatorial objects has been thriving for the last decade or so. The syntactic, algebraic approach to the subject is popularly known as ‘flag algebras’, while the semantic, geometric approach is often associated with the name ‘graph limits’. The language of graph limits is generally more intuitive and expressible, but a price that one has to pay for it is that it is better suited for the case of ordinary graphs than for more general combinatorial objects. Accordingly, there have been several attempts in the literature, of varying degree of generality, to define limit objects for more complicated combinatorial structures. This paper is another attempt at a workable general theory of dense limit objects. Unlike previous efforts in this direction (with the notable exception of [5] by Aroskar and Cummings), our account is based on the same concepts from first-order logic and model theory as in the theory of flag algebras. It is shown how our definitions naturally encompass a host of previously considered cases (graphons, hypergraphons, digraphons, permutons, posetons, coloured graphs, and so on), and the fundamental properties of existence and uniqueness are extended to this more general case. Also given is an intuitive general proof of the continuous version of the Induced Removal Lemma based on the compactness theorem for propositional calculus. Use is made of the notion of open interpretation that often allows one to transfer methods and results from one situation to another. Again, it is shown that some previous arguments can be quite naturally framed using this language. Bibliography: 68 titles.

Détail

Keywords: model theory, graph limits, flag algebras, exchangeable arrays, extremal combinatorics.

Bibliographie

[1] N. Ackerman, C. Freer, R. Patel, “Invariant measures concentrated on countable structures”, Forum Math. Sigma, 4 (2016), e17, 59 pp. | DOI | MR | Zbl

[2] D. J. Aldous, “Representations for partially exchangeable arrays of random variables”, J. Multivariate Anal., 11:4 (1981), 581–598 | DOI | MR | Zbl

[3] D. J. Aldous, “Exchangeability and related topics”, École d'été de probabilités de Saint-Flour XIII – 1983, Lecture Notes in Math., 1117, Springer, Berlin, 1985, 1–198 | DOI | MR | Zbl

[4] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., 3rd ed., John Wiley Sons, Inc., Hoboken, NJ, 2008, xviii+352 pp. ; N. Alon, Dzh. Spenser, Veroyatnostnyi metod, Binom. Laboratoriya znanii, M., 2007, 320 pp. | DOI | MR | Zbl

[5] A. Aroskar, J. Cummings, “Limits, regularity and removal for finite structures”, 2014, 26 pp., arXiv: 1412.8084

[6] T. Austin, “On exchangeable random variables and the statistics of large graphs and hypergraphs”, Probab. Surv., 5 (2008), 80–145 | DOI | MR | Zbl

[7] T. Austin, T. Tao, “Testability and repair of hereditary hypergraph properties”, Random Structures Algorithms, 36:4 (2010), 373–463 | DOI | MR | Zbl

[8] R. Baber, Some results in extremal combinatorics, Thesis (Ph.D.), Univ. of London, Univ. College London (UK), 2011, 149 pp. | MR

[9] J. Balogh, P. Hu, B. Lidický, H. Liu, “Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube”, European J. Combin., 35 (2014), 75–85 | DOI | MR | Zbl

[10] J. Balogh, P. Hu, B. Lidický, F. Pfender, J. Volec, M. Young, “Rainbow triangles in three-colored graphs”, J. Combin. Theory Ser. B, 126 (2017), 83–113 | DOI | MR | Zbl

[11] J. Barwise (ed.), Handbook of mathematical logic, Stud. Logic Found. Math., 90, North-Holland Publishing Co., Amsterdam, 1977, xi+1165 pp. | MR | MR | MR | MR | MR | Zbl | Zbl

[12] V. I. Bogachev, Measure theory, v. I, II, Springer-Verlag, Berlin, 2007, xviii+500 pp., xiv+575 pp. | DOI | MR | Zbl

[13] B. Bollobás, O. Riordan, “Metrics for sparse graphs”, Surveys in combinatorics 2009, London Math. Soc. Lecture Note Ser., 365, Cambridge Univ. Press, Cambridge, 2009, 211–287 | DOI | MR | Zbl

[14] B. Bollobás, O. Riordan, “Sparse graphs: metrics and random models”, Random Structures Algorithms, 39:1 (2011), 1–38 | DOI | MR | Zbl

[15] C. Borgs, J. T. Chayes, H. Cohn, Y. Zhao, “An {$L^p$} theory of sparse graph convergence. I. Limits, sparse random graph models, and power law distributions”, Trans. Amer. Math. Soc., 372:5 (2019), 3019–3062 ; (2014), 44 pp., arXiv: 1401.2906 | DOI | MR | Zbl

[16] C. Borgs, J. T. Chayes, H. Cohn, Y. Zhao, “An $L^p$ theory of sparse graph convergence. II. LD convergence, quotients and right convergence”, Ann. Probab., 46:1 (2018), 337–396 | DOI | MR | Zbl

[17] C. Borgs, J. T. Chayes, L. Lovász, V. Sós, K. Vesztergombi, “Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing”, Adv. Math., 219:6 (2008), 1801–1851 | DOI | MR | Zbl

[18] P. Brass, G. Károlyi, P. Valtr, “A Turán-type extremal theory of convex geometric graphs”, Discrete and computational geometry, Algorithms Combin., 25, Springer, Berlin, 2003, 275–300 | DOI | MR | Zbl

[19] L. Caccetta, R. Häggkvist, “On minimal digraphs with given girth”, Proceedings of the 9th southeastern conference on combinatorics, graph theory, and computing (Florida Atlantic Univ., Boca Raton, FL, 1978), Congress. Numer., 21, Utilitas Math., Winnipeg, MB, 1978, 181–187 | MR | Zbl

[20] P. J. Cameron, “The random graph”, The mathematics of Paul Erdős, v. II, Algorithms Combin., 14, Springer, Berlin, 1997, 333–351 | DOI | MR | Zbl

[21] C. C. Chang, H. J. Keisler, Model theory, Stud. Logic Found. Math., 73, North-Holland Publishing Co., Amsterdam–London; American Elsevier Publishing Co., Inc., New York, 1973, xii+550 pp. | MR | MR | Zbl

[22] S. Chatterjee, A. Dembo, “Nonlinear large deviations”, Adv. Math., 299 (2016), 396–450 | DOI | MR | Zbl

[23] F. R. K. Chung, R. L. Graham, “Quasi-random tournaments”, J. Graph Theory, 15:2 (1991), 173–198 | DOI | MR | Zbl

[24] F. R. K. Chung, R. L. Graham, R. M. Wilson, “Quasi-random graphs”, Combinatorica, 9 (1989), 345–362 | DOI | MR | Zbl

[25] P. Diaconis, D. Freedman, “On the statistics of vision: the Julesz conjecture”, J. Math. Psych., 24:2 (1981), 112–138 | DOI | MR | Zbl

[26] P. Diaconis, D. Freedman, “Partial exchangeability and sufficiency”, Statistics: applications and new directions (Calcutta, 1981), Indian Statist. Inst., Calcutta, 1984, 205–236 | MR | Zbl

[27] P. Diaconis, S. Holmes, S. Janson, “Threshold graph limits and random threshold graphs”, Internet Math., 5:3 (2008), 267–320 | DOI | MR | Zbl

[28] P. Diaconis, S. Holmes, S. Janson, “Interval graph limits”, Ann. Comb., 17:1 (2013), 27–52 | DOI | MR | Zbl

[29] P. Diaconis, S. Janson, “Graph limits and exchangeable random graphs”, Rend. Mat. Appl. (7), 28:1 (2008), 33–61 | MR | Zbl

[30] G. Elek, B. Szegedy, “A measure-theoretic approach to the theory of dense hypergraphs”, Adv. Math., 231:3-4 (2012), 1731–1772 | DOI | MR | Zbl

[31] D. G. Fon-der-Flaass, “Method for construction of $(3,4)$-graphs”, Math. Notes, 44:4 (1988), 781–783 | DOI | MR | Zbl

[32] W. T. Gowers, “Quasirandomness, counting and regularity for 3-uniform hypergraphs”, Combin. Probab. Comput., 15:1-2 (2006), 143–184 | DOI | MR | Zbl

[33] H. Hatami, P. Hatami, J. Hirst, “Limits of boolean functions on $\mathbb F_p^n$”, Electron. J. Combin., 21:4 (2014), P4.2, 15 pp. | DOI | MR | Zbl

[34] H. Hatami, S. Norine, “Undecidability of linear inequalities in graph homomorphism densities”, J. Amer. Math. Soc., 24:2 (2011), 547–565 | DOI | MR | Zbl

[35] J. Hladký, A. Máthé, V. Patel, O. Pikhurko, “Poset limits can be totally ordered”, Trans. Amer. Math. Soc., 367:6 (2015), 4319–4337 | DOI | MR | Zbl

[36] D. N. Hoover, Relations on probability spaces and arrays of random variables, Preprint, Institute for Advanced Study, Princeton, NJ, 1979, 63 pp.

[37] C. Hoppen, Y. Kohayakawa, C. G. Moreira, B. Ráth, R. Menezes Sampaio, “Limits of permutation sequences”, J. Combin. Theory Ser. B, 103:1 (2013), 93–113 | DOI | MR | Zbl

[38] S. Janson, “Poset limits and exchangeable random posets”, Combinatorica, 31:5 (2011), 529–563 | DOI | MR | Zbl

[39] S. Janson, “Quasi-random graphs and graph limits”, European J. Combin., 32:7 (2011), 1054–1083 | DOI | MR | Zbl

[40] G. Japaridze, D. de Jongh, “The logic of provability”, Handbook of proof theory, Stud. Logic Found. Math., 137, North-Holland, Amsterdam, 1998, 475–546 | DOI | MR | Zbl

[41] O. Kallenberg, “Symmetries on random arrays and set-indexed processes”, J. Theoret. Probab., 5:4 (1992), 727–765 | DOI | MR | Zbl

[42] O. Kallenberg, Probabilistic symmetries and invariance principles, Probab. Appl. (N. Y.), Springer, New York, 2005, xii+510 pp. | DOI | MR | Zbl

[43] P. Keevash, “Hypergraph Turán problems”, Surveys in combinatorics 2011 (Exeter, UK), London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011, 83–139 | MR | Zbl

[44] L. Lovász, Large networks and graph limits, Amer. Math. Soc. Colloq. Publ., 60, Amer. Math. Soc., Providence, RI, 2012, xiv+475 pp. | DOI | MR | Zbl

[45] L. Lovász, B. Szegedy, “Limits of dense graph sequences”, J. Combin. Theory Ser. B, 96:6 (2006), 933–957 | DOI | MR | Zbl

[46] L. Lovász, B. Szegedy, “Finitely forcible graphons”, J. Combin. Theory Ser. B, 101:5 (2011), 269–301 | DOI | MR | Zbl

[47] M. Malliaris, S. Shelah, “Regularity lemmas for stable graphs”, Trans. Amer. Math. Soc., 366:3 (2014), 1551–1585 | DOI | MR | Zbl

[48] D. Mubayi, A. Razborov, Polynomial to exponential transition in Ramsey theory, 2020 (v1 – 2019), 27 pp., arXiv: 1901.06029

[49] J. C. Oxtoby, Measure and category, A survey of the analogies between topological and measure spaces, Grad. Texts in Math., 2, 2nd ed., Springer-Verlag, New York–Berlin, 1980, x+106 pp. ; Dzh. Okstobi, Mera i kategoriya, Sovremennaya matematika, Mir, M., 1974, 158 pp. | DOI | MR | Zbl

[50] J. Pach, G. Tardos, “Forbidden paths and cycles in ordered graphs and matrices”, Israel J. Math., 155 (2006), 359–380 | DOI | MR | Zbl

[51] F. Petrov, General removal lemma, 2013, 5 pp., arXiv: 1309.3795

[52] F. Petrov, A. Vershik, “Uncountable graphs and invariant measures on the set of universal countable graphs”, Random Structures Algorithms, 37:3 (2010), 389–406 | DOI | MR | Zbl

[53] M. O. Rabin, “Decidable theories”, Handbook of mathematical logic, Part III, Stud. Logic Found. Math., 90, North-Holland Publishing Co., Amsterdam, 1977, 595–629 | MR

[54] A. A. Razborov, “Flag algebras”, J. Symbolic Logic, 72:4 (2007), 1239–1282 | DOI | MR | Zbl

[55] A. A. Razborov, “On the Fon-der-Flaass interpretation of extremal examples for Turan's $(3,4)$-problem”, Proc. Steklov Inst. Math., 274 (2011), 247–266 | DOI | MR | Zbl

[56] A. A. Razborov, “Flag algebras: an interim report”, The mathematics of Paul Erdös II, 2nd ed., Springer, New York, 2013, 207–232 | DOI | MR

[57] V. Rödl, M. Schacht, “Generalizations of the removal lemma”, Combinatorica, 29:4 (2009), 467–501 | DOI | MR | Zbl

[58] W. Rudin, Functional analysis, Internat. Ser. Pure Appl. Math., 2nd ed., McGraw-Hill, Inc., 1991, xviii+424 pp. ; U. Rudin, Funktsionalnyi analiz, Mir, M., 1975, 443 pp. | MR | Zbl | MR

[59] A. Saad, J. Wolf, “Ramsey multiplicity of linear patterns in certain finite abelian groups”, Q. J. Math., 68:1 (2017), 125–140 | DOI | MR | Zbl

[60] J. R. Shoenfield, Mathematical logic, Addison-Wesley Publishing Co., Reading, MA–London–Don Mills, ON, 1967, viii+344 pp. | MR | MR | Zbl

[61] E. Spiegel, Ch. J. O'Donnell, Incidence algebras, Monogr. Textbooks Pure Appl. Math., 206, Marcel Dekker, Inc., New York, 1997, x+335 pp. | MR | Zbl

[62] B. Szegedy, Gowers norms, regularization and limits of functions on abelian groups, 2010, 35 pp., arXiv: 1010.6211

[63] G. Tardos, “Extremal theory of ordered graphs”, Proceedings of the international congress of mathematicians (Rio de Janeiro, 2018), v. 4, World Sci. Publ., Hackensack, NJ, 2018, 3235–3243 | MR

[64] A. Tarski, A. Mostowski, R. M. Robinson, Undecidable theories, Stud. Logic Found. Math., North-Holland Publishing Co., Amsterdam, 1953, xi+98 pp. | MR | Zbl

[65] A. Thomason, “Pseudo-random graphs”, Random graphs' 85 (Poznań, 1985), North-Holland Math. Stud., 144, Ann. Discrete Math., 33, North-Holland, Amsterdam, 1987, 307–331 | MR | Zbl

[66] P. Turán, “Egy gráfelméleti szélsöérték feladatról”, Mat. Fiz. Lapok, 48 (1941), 436–452 | MR | Zbl

[67] A. M. Vershik, “Classification of measurable functions of several variables and invariantly distributed random matrices”, Funct. Anal. Appl., 36:2 (2002), 93–105 | DOI | DOI | MR | Zbl

[68] Yu. Yoshida, “Gowers norm, function limits, and parameter estimation”, Proceedings of the 27th annual ACM–SIAM symposium on discrete algorithms, ACM, New York, 2016, 1391–1406 | DOI | MR | Zbl