AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth
About this Title
Jaroslav Nešetřil, Jaroslav Nešetřil, Computer Science Institute of Charles University (IUUK and ITI), Malostranské nám.25, 11800 Praha 1, Czech Republic and Patrice Ossona de Mendez, Patrice Ossona de Mendez, Centre d’Analyse et de Mathématiques Sociales (CNRS, UMR 8557), 190-198 avenue de France, 75013 Paris, France
Publication: Memoirs of the American Mathematical Society
Publication Year:
2020; Volume 263, Number 1272
ISBNs: 978-1-4704-4065-7 (print); 978-1-4704-5652-8 (online)
DOI: https://doi.org/10.1090/memo/1272
Published electronically: February 26, 2020
Keywords: Graph and relational structure,
graph limits,
structural limits,
Radon measures,
Stone space,
model theory,
first-order logic,
measurable graph
MSC: Primary 03C13, 03C98, 05C99, 06E15; Secondary 28C05
Table of Contents
Chapters
- 1. Introduction
- 2. General Theory
- 3. Modelings for Sparse Structures
- 4. Limits of Graphs with Bounded Tree-depth
- 5. Concluding Remarks
Abstract
In this paper we introduce a general framework for the study of limits of relational structures and graphs in particular, which is based on a combination of model theory and (functional) analysis. We show how the various approaches to graph limits fit to this framework and that they naturally appear as “tractable cases” of a general theory. As an outcome of this, we provide extensions of known results. We believe that this puts these into a broader context. The second part of the paper is devoted to the study of sparse structures. First, we consider limits of structures with bounded diameter connected components and we prove that in this case the convergence can be “almost” studied component-wise. We also propose the structure of limit objects for convergent sequences of sparse structures. Eventually, we consider the specific case of limits of colored rooted trees with bounded height and of graphs with bounded tree-depth, motivated by their role as “elementary bricks” these graphs play in decompositions of sparse graphs, and give an explicit construction of a limit object in this case. This limit object is a graph built on a standard probability space with the property that every first-order definable set of tuples is measurable. This is an example of the general concept of modeling we introduce here. Our example is also the first “intermediate class” with explicitly defined limit structures where the inverse problem has been solved.- Scott Adams, Trees and amenable equivalence relations, Ergodic Theory Dynam. Systems 10 (1990), no. 1, 1–14. MR 1053796, DOI 10.1017/S0143385700005368
- Hans Adler and Isolde Adler, Interpreting nowhere dense graph classes as a classical notion of model theory, European J. Combin. 36 (2014), 322–330. MR 3131898, DOI 10.1016/j.ejc.2013.06.048
- David J. Aldous, Representations for partially exchangeable arrays of random variables, J. Multivariate Anal. 11 (1981), no. 4, 581–598. MR 637937, DOI 10.1016/0047-259X(81)90099-3
- David J. Aldous, Exchangeability and related topics, École d’été de probabilités de Saint-Flour, XIII—1983, Lecture Notes in Math., vol. 1117, Springer, Berlin, 1985, pp. 1–198. MR 883646, DOI 10.1007/BFb0099421
- David Aldous and Russell Lyons, Processes on unimodular random networks, Electron. J. Probab. 12 (2007), no. 54, 1454–1508. MR 2354165, DOI 10.1214/EJP.v12-463
- Ashwini Aroskar, Limits, Regularity and Removal for Relational and Weighted Structures, ProQuest LLC, Ann Arbor, MI, 2012. Thesis (Ph.D.)–Carnegie Mellon University. MR 3068004
- A. Aroskar and J. Cummings, Limits, regularity and removal for finite structures, arXiv:1412.8084, 2014, to appear in The Journal of Symbolic Logic.
- Tim Austin, On exchangeable random variables and the statistics of large graphs and hypergraphs, Probab. Surv. 5 (2008), 80–145. MR 2426176, DOI 10.1214/08-PS124
- Itai Benjamini, Hilary Finucane, and Romain Tessera, On the scaling limit of finite vertex transitive graphs with large diameter, Combinatorica 37 (2017), no. 3, 333–374. MR 3666783, DOI 10.1007/s00493-015-2975-4
- Itai Benjamini and Oded Schramm, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001), no. 23, 13. MR 1873300, DOI 10.1214/EJP.v6-96
- Andreas Blass, Geoffrey Exoo, and Frank Harary, Paley graphs satisfy all first-order adjacency axioms, J. Graph Theory 5 (1981), no. 4, 435–439. MR 635707, DOI 10.1002/jgt.3190050414
- Béla Bollobás and Andrew Thomason, Graphs which contain all small graphs, European J. Combin. 2 (1981), no. 1, 13–15. MR 611926, DOI 10.1016/S0195-6698(81)80015-7
- 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
- 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
- Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi, Counting graph homomorphisms, Topics in discrete mathematics, Algorithms Combin., vol. 26, Springer, Berlin, 2006, pp. 315–371. MR 2249277, DOI 10.1007/3-540-33700-8_{1}8
- 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
- Peter J. Cameron and Jaroslav Nešetřil, Homomorphism-homogeneous relational structures, Combin. Probab. Comput. 15 (2006), no. 1-2, 91–103. MR 2195577, DOI 10.1017/S0963548305007091
- Ashok K. Chandra and Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977) Assoc. Comput. Mach., New York, 1977, pp. 77–90. MR 0489103
- P. Charbit, L. Hosseini, and P. Ossona de Mendez, Limits of structures and the example of tree semi-lattices, Discrete Math. 340 (2017), no. 10, 2589–2603. MR 3674160, DOI 10.1016/j.disc.2017.06.013
- Gregory Cherlin, Two problems on homogeneous structures, revisited, Model theoretic methods in finite combinatorics, Contemp. Math., vol. 558, Amer. Math. Soc., Providence, RI, 2011, pp. 319–415. MR 3418640, DOI 10.1090/conm/558/11055
- Demetres Christofides and Daniel Král’, First-order convergence and roots, Combin. Probab. Comput. 25 (2016), no. 2, 213–221. MR 3455674, DOI 10.1017/S0963548315000048
- 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
- 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
- Persi Diaconis and Svante Janson, Graph limits and exchangeable random graphs, Rend. Mat. Appl. (7) 28 (2008), no. 1, 33–61. MR 2463439
- Reinhard Diestel, Graphentheorie, Springer-Lehrbuch. [Springer Textbook], Springer-Verlag, Berlin, 1996 (German). MR 1411445
- Z. Dvořák, Asymptotical structure of combinatorial objects, Ph.D. thesis, Charles University, Faculty of Mathematics and Physics, 2007.
- Zdeněk Dvořák, On forbidden subdivision characterizations of graph classes, European J. Combin. 29 (2008), no. 5, 1321–1332. MR 2419233, DOI 10.1016/j.ejc.2007.05.008
- A. Ehrenfeucht, An application of games to the completeness problem for formalized theories, Fund. Math. 49 (1960/61), 129–141. MR 126370, DOI 10.4064/fm-49-2-129-141
- Michael Elberfeld, Martin Grohe, and Till Tantau, Where first-order and monadic second-order logic coincide, Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE Computer Soc., Los Alamitos, CA, 2012, pp. 265–274. MR 3050447, DOI 10.1109/LICS.2012.37
- Gábor Elek, On limits of finite graphs, Combinatorica 27 (2007), no. 4, 503–507. MR 2359831, DOI 10.1007/s00493-007-2214-8
- G. Elek and B. Szegedy, Limits of hypergraphs, removal and regularity lemmas. A non-standard approach, arXiv:0705.2179v1 [math.CO], 2007.
- P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 125031
- P. Erdős and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963), 295–315. MR 156334, DOI 10.1007/BF01895716
- Ronald Fagin, Probabilities on finite models, J. Symbolic Logic 41 (1976), no. 1, 50–58. MR 476480, DOI 10.2307/2272945
- R. Fraïssé, Sur une nouvelle classification des systèmes de relations, Comptes rendus hebdomadaires des séances de l’Académie des Sciences 230 (1950), 1022–1024.
- Roland Fraïssé, Sur quelques classifications des systèmes de relations, Publ. Sci. Univ. Alger. Sér. A 1 (1954), 35–182 (1955) (French). MR 69236
- D. Gaboriau, Invariant percolation and harmonic Dirichlet functions, Geom. Funct. Anal. 15 (2005), no. 5, 1004–1051. MR 2221157, DOI 10.1007/s00039-005-0539-2
- Haim Gaifman, On local and nonlocal properties, Proceedings of the Herbrand symposium (Marseilles, 1981) Stud. Logic Found. Math., vol. 107, North-Holland, Amsterdam, 1982, pp. 105–135. MR 757024, DOI 10.1016/S0049-237X(08)71879-2
- Jakub Gajarský, Petr Hliněný, Tomáš Kaiser, Daniel Kráľ, Martin Kupec, Jan Obdržálek, Sebastian Ordyniak, and Vojtěch Tůma, First order limits of sparse graphs: plane trees and path-width, Random Structures Algorithms 50 (2017), no. 4, 612–635. MR 3660522, DOI 10.1002/rsa.20676
- Robert Ganian, Petr Hliněný, Jaroslav Nešetril, Jan Obdržálek, Patrice Ossona de Mendez, and Reshma Ramadurai, When trees grow low: shrubs and fast $\textrm {MSO}_1$, Mathematical foundations of computer science 2012, Lecture Notes in Comput. Sci., vol. 7464, Springer, Heidelberg, 2012, pp. 419–430. MR 3030450, DOI 10.1007/978-3-642-32589-2_{3}8
- Ju. V. Glebskiĭ, D. I. Kogan, M. I. Liogon′kiĭ, and V. A. Talanov, Volume and fraction of satisfiability of formulas of the lower predicate calculus, Kibernetika (Kiev) 2 (1969), 17–27 (Russian, with English summary). MR 300882
- Martin Grohe and Stephan Kreutzer, Methods for algorithmic meta theorems, Model theoretic methods in finite combinatorics, Contemp. Math., vol. 558, Amer. Math. Soc., Providence, RI, 2011, pp. 181–205. MR 3418636, DOI 10.1090/conm/558/11051
- William Hanf, Model-theoretic methods in the study of elementary logic, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 132–145. MR 0210570
- Hamed Hatami and Serguei Norine, The entropy of random-free graphons and properties, Combin. Probab. Comput. 22 (2013), no. 4, 517–526. MR 3073488, DOI 10.1017/S0963548313000175
- Pavol Hell and Jaroslav Nešetřil, Graphs and homomorphisms, Oxford Lecture Series in Mathematics and its Applications, vol. 28, Oxford University Press, Oxford, 2004. MR 2089014
- Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741
- D. Hoover, Relations on probability spaces and arrays of random variables, Tech. report, Institute for Advanced Study, Princeton, NJ, 1979.
- L. Hosseini, J. Nešetřil, and P. Ossona de Mendez, Approximation of mappings, 2017+, in preparation.
- J. Hubička and J. Nešetřil, Universal structures with forbidden homomorphisms, Ontos Mathematical Logic (Å. Hirvonen, J. Kontinen, R. Kossak, and A. Villaveces, eds.), vol. 5, de Gruyter, 2015, pp. 241–264.
- Svante Janson, Graphons, cut norm and distance, couplings and rearrangements, New York Journal of Mathematics. NYJM Monographs, vol. 4, State University of New York, University at Albany, Albany, NY, 2013. MR 3043217
- Svante Janson, Graph limits and hereditary properties. part B, European J. Combin. 52 (2016), no. part B, 321–337. MR 3425983, DOI 10.1016/j.ejc.2015.07.010
- Olav Kallenberg, Probabilistic symmetries and invariance principles, Probability and its Applications (New York), Springer, New York, 2005. MR 2161313
- František Kardoš, Daniel Král’, Anita Liebenau, and Lukáš Mach, First order convergence of matroids, European J. Combin. 59 (2017), 150–168. MR 3546908, DOI 10.1016/j.ejc.2016.08.005
- A. S. Kechris, S. Solecki, and S. Todorcevic, Borel chromatic numbers, Adv. Math. 141 (1999), no. 1, 1–44. MR 1667145, DOI 10.1006/aima.1998.1771
- A. H. Lachlan and Robert E. Woodrow, Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc. 262 (1980), no. 1, 51–94. MR 583847, DOI 10.1090/S0002-9947-1980-0583847-2
- Daniel Lascar, La théorie des modèles en peu de maux, Nouvelle Bibliothèque Mathématique [New Mathematics Library], vol. 10, Cassini, Paris, 2009 (French). MR 3408502
- Michael C. Laskowski, Vapnik-Chervonenkis classes of definable sets, J. London Math. Soc. (2) 45 (1992), no. 2, 377–384. MR 1171563, DOI 10.1112/jlms/s2-45.2.377
- Peter A. Loeb, Conversion from nonstandard to standard measure spaces and applications in probability theory, Trans. Amer. Math. Soc. 211 (1975), 113–122. MR 390154, DOI 10.1090/S0002-9947-1975-0390154-8
- Jerzy Łoś, Quelques remarques, théorèmes et problèmes sur les classes définissables d’algèbres, Mathematical interpretation of formal systems, North-Holland Publishing Co., Amsterdam, 1955, pp. 98–113 (French). MR 0075156
- László Lovász, Very large graphs, Current developments in mathematics, 2008, Int. Press, Somerville, MA, 2009, pp. 67–128. MR 2555927
- 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 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, Regularity partitions and the topology of graphons, An irregular mind, Bolyai Soc. Math. Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 415–446. MR 2815610, DOI 10.1007/978-3-642-14444-8_{1}2
- Russell Lyons, Asymptotic enumeration of spanning trees, Combin. Probab. Comput. 14 (2005), no. 4, 491–522. MR 2160416, DOI 10.1017/S096354830500684X
- J. Nešetřil and P. Ossona de Mendez, The grad of a graph and classes with bounded expansion, 7th International Colloquium on Graph Theory (A. Raspaud and O. Delmas, eds.), Electronic Notes in Discrete Mathematics, vol. 22, Elsevier, 2005, pp. 101–106.
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Linear time low tree-width partitions and algorithmic consequences, STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 391–400. MR 2277165, DOI 10.1145/1132516.1132575
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Tree-depth, subgraph coloring and homomorphism bounds, European J. Combin. 27 (2006), no. 6, 1022–1041. MR 2226435, DOI 10.1016/j.ejc.2005.01.010
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Grad and classes with bounded expansion. I. Decompositions, European J. Combin. 29 (2008), no. 3, 760–776. MR 2397335, DOI 10.1016/j.ejc.2006.07.013
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Grad and classes with bounded expansion. II. Algorithmic aspects, European J. Combin. 29 (2008), no. 3, 777–791. MR 2397336, DOI 10.1016/j.ejc.2006.07.014
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Grad and classes with bounded expansion. III. Restricted graph homomorphism dualities, European J. Combin. 29 (2008), no. 4, 1012–1024. MR 2408375, DOI 10.1016/j.ejc.2007.11.019
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Fraternal augmentations, arrangeability and linear Ramsey numbers, European J. Combin. 30 (2009), no. 7, 1696–1703. MR 2548660, DOI 10.1016/j.ejc.2009.03.012
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Extremal problems for sparse graphs, An irregular mind, Bolyai Soc. Math. Stud., vol. 21, János Bolyai Math. Soc., Budapest, 2010, pp. 447–490. MR 2815611, DOI 10.1007/978-3-642-14444-8_{1}3
- Jaroslav Nešetřil and Patrice Ossona de Mendez, First order properties on nowhere dense structures, J. Symbolic Logic 75 (2010), no. 3, 868–887. MR 2723771, DOI 10.2178/jsl/1278682204
- Jaroslav Nešetřil and Patrice Ossona de Mendez, From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits, European Congress of Mathematics, Eur. Math. Soc., Zürich, 2010, pp. 135–165. MR 2648324, DOI 10.4171/077-1/7
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Sparse combinatorial structures: classification and applications, Proceedings of the International Congress of Mathematicians. Volume IV, Hindustan Book Agency, New Delhi, 2010, pp. 2502–2529. MR 2827982
- Jaroslav Nešetřil and Patrice Ossona de Mendez, How many $F$’s are there in $G$?, European J. Combin. 32 (2011), no. 7, 1126–1141. MR 2825539, DOI 10.1016/j.ejc.2011.03.007
- Jaroslav Nešetřil and Patrice Ossona de Mendez, On nowhere dense graphs, European J. Combin. 32 (2011), no. 4, 600–617. MR 2780859, DOI 10.1016/j.ejc.2011.01.006
- Jaroslav Nešetřil and Patrice Ossona de Mendez, A model theory approach to structural limits, Comment. Math. Univ. Carolin. 53 (2012), no. 4, 581–603. MR 3016428
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Sparsity, Algorithms and Combinatorics, vol. 28, Springer, Heidelberg, 2012. Graphs, structures, and algorithms. MR 2920058
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Existence of modeling limits for sequences of sparse structures, J. Symb. Log. 84 (2019), no. 2, 452–472. MR 3961608, DOI 10.1017/jsl.2018.32
- Jaroslav Nešetřil and Patrice Ossona de Mendez, First-order limits, an analytical perspective. part B, European J. Combin. 52 (2016), no. part B, 368–388. MR 3425985, DOI 10.1016/j.ejc.2015.07.012
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Modeling limits in hereditary classes: reduction and application to trees, Electron. J. Combin. 23 (2016), no. 2, Paper 2.52, 33. MR 3522136
- Ya. Neshetril and P. Ossona de Mendez, Structural sparsity, Uspekhi Mat. Nauk 71 (2016), no. 1(427), 85–116 (Russian, with Russian summary); English transl., Russian Math. Surveys 71 (2016), no. 1, 79–107. MR 3507464, DOI 10.4213/rm9688
- Jaroslav Nešetřil and Patrice Ossona de Mendez, Cluster analysis of local convergent sequences of structures, Random Structures Algorithms 51 (2017), no. 4, 674–728. MR 3718594, DOI 10.1002/rsa.20719
- Lucas Hosseini, Jaroslav Nešetřil, and Patrice Ossona de Mendez, Limits of mappings, European J. Combin. 66 (2017), 145–159. MR 3692143, DOI 10.1016/j.ejc.2017.06.021
- Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R. Wood, Characterisations and examples of graph classes with bounded expansion, European J. Combin. 33 (2012), no. 3, 350–373. MR 2864421, DOI 10.1016/j.ejc.2011.09.008
- Oleg Pikhurko, An analytic approach to stability, Discrete Math. 310 (2010), no. 21, 2951–2964. MR 2677656, DOI 10.1016/j.disc.2010.07.002
- M. H. Stone, The theory of representations for Boolean algebras, Trans. Amer. Math. Soc. 40 (1936), no. 1, 37–111. MR 1501865, DOI 10.1090/S0002-9947-1936-1501865-8
- B. A. Trahtenbrot, The impossibility of an algorithm for the decision problem for finite domains, Doklady Akad. Nauk SSSR (N.S.) 70 (1950), 569–572 (Russian). MR 0033784
- Yufei Zhao, Hypergraph limits: a regularity approach, Random Structures Algorithms 47 (2015), no. 2, 205–226. MR 3382671, DOI 10.1002/rsa.20537