Structural sparsity

J. Nešetřil   ; P. Ossona de Mendez

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 71 (2016) no. 1, pp. 79-107

Résumé

The notion of structural sparsity is discussed, and its relation to the ‘nowhere dense/somewhere dense’ dichotomy introduced by the authors for classes of graphs is examined. The numerous facets of this dichotomy are surveyed, along with its connections to several concepts like stability, independence, VC-dimension, regularity partitions, entropy, class speed, low tree-depth decomposition, quasi-wideness, neighbourhood covering, subgraph statistics, and so on, as well as algorithmic complexity issues like fixed-parameter tractability of first-order model checking. Bibliography: 78 titles.

Détail

Keywords: graph theory, nowhere dense class, sparsity, stability, independence property, shallow minor, random-free limit, structural limit, modelling, low tree-depth decomposition, model checking.
Mots-clés : relational structures, VC-dimension, Borel structure

Bibliographie

[1] N. Ackerman, C. Freer, R. Patel, Invariant measures concentrated on countable structures, 2012 (v3 – 2014), 48 pp., arXiv: 1206.4011v1

[2] H. Adler, I. Adler, “Interpreting nowhere dense graph classes as a classical notion of model theory”, European J. Combin., 36 (2014), 322–330 | DOI | MR | Zbl

[3] J. Alber, M. R. Fellows, R. Niedermeier, “Polynomial-time data reduction for dominating set”, J. ACM, 51:3 (2004), 363–384 (electronic) | DOI | MR | Zbl

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

[5] D. J. Aldous, “Exchangeability and continuum limits of discrete random structures”, Proceedings of the International congress of mathematicians 2010 (ICM 2010) (Hyderabad, 2010), v. I, Hindustan Book Agency, New Delhi, 2011, 141–153 | DOI | MR | Zbl

[6] V. E. Alekseev, “On the entropy values of hereditary classes of graphs”, Discrete Math. Appl., 3:2 (1993), 191–199 | DOI | MR | Zbl

[7] N. Alon, R. A. Duke, H. Lefmann, V. Rödl, R. Yuster, “The algorithmic aspects of the regularity lemma”, J. Algorithms, 16:1 (1994), 80–109 | DOI | MR | Zbl

[8] N. Alon, C. McDiarmid, B. Reed, “Star arboricity”, Combinatorica, 12:4 (1992), 375–380 | DOI | MR | Zbl

[9] J. Balogh, B. Bollobás, D. Weinreich, “The penultimate rate of growth for graph properties”, European J. Combin., 22:3 (2001), 277–289 | DOI | MR | Zbl

[10] H. L. Bodlaender, J. S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller, Zs. Tuza, “Rankings of graphs”, Graph-theoretic concepts in computer science (Herrsching, 1994), Lecture Notes in Comput. Sci., 903, Springer, Berlin, 1995, 292–304 | DOI | MR

[11] H. L. Bodlaender, F. V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, D. M. Thilikos, “(Meta) kernelization”, 2009 50th annual IEEE symposium on foundations of computer science (FOCS 2009), IEEE Computer Soc., Los Alamitos, CA, 2009, 629–638 | DOI | MR | Zbl

[12] C. Borgs, J. Chayes, L. Lovász, V. T. Sós, K. Vesztergombi, “Counting graph homomorphisms”, Topics in discrete mathematics, Algorithms Combin., 26, Springer, Berlin, 2006, 315–371 | DOI | MR | Zbl

[13] N. Bousquet, S. Thomassé, VC-dimension and Erdős–Pósa property, 2014, 21 pp., arXiv: 1412.1793v1

[14] E. Candès, “Mathematics of sparsity (and a few other things)”, Proceedings of the International congress of mathematicians 2014 (ICM 2014) (Seoul, 2014), v. I, KYUNG MOON SA Co. Ltd., Seoul, 2014, 235–258 \par http://www.icm2014.org/en/vod/proceedings

[15] S. Chatterjee, P. Diaconis, “Estimating and understanding exponential random graph models”, Ann. Statist., 41:5 (2013), 2428–2461 | DOI | MR | Zbl

[16] S. Chatterjee, S. R. S. Varadhan, “The large deviation principle for the Erdős–Rényi random graph”, European J. Combin., 32:7 (2011), 1000–1017 | DOI | MR | Zbl

[17] B. Chazelle, E. Welzl, “Quasi-optimal range searching in spaces of finite VC-dimension”, Discrete Comput. Geom., 4:5 (1989), 467–489 | DOI | MR | Zbl

[18] A. Dawar, “Finite model theory on tame classes of structures”, Mathematical foundations of computer science 2007 (MFCS 2007), Lecture Notes in Comput. Sci., 4708, Springer, Berlin, 2007, 2–12 | DOI | MR | Zbl

[19] A. Dawar, S. Kreutzer, “Domination problems in nowhere-dense classes of graphs”, Foundations of software technology and theoretical computer science (FSTTCS 2009), LIPIcs. Leibniz Int. Proc. Inform., 4, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2009, 157–168 | DOI | MR | Zbl

[20] J. S. Deogun, T. Kloks, D. Kratsch, H. Müller, “On vertex ranking for permutation and other graphs”, STACS 94 Proceedings of the 11th annual symposium on theoretical aspects of computer science (Caen, 1994), Lecture Notes in Comput. Sci., 775, Springer, Berlin, 1994, 747–758 | DOI | MR | Zbl

[21] P. G. Drange, M. S. Dregi, F. V. Fomin, S. Kreutzer, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, F. Reidl, S. Saurabh, F. Sánchez Villaamil, S. Sikdar, Kernelization and sparseness: the case of dominating set, 2014 (v2 – 2015), 42 pp., arXiv: 1411.4575v1

[22] Z. Dvořák, Asymptotical structure of combinatorial objects, Ph. D. thesis, Charles Univ., Faculty of mathematics and physics, Prague, 2007, 102 pp.

[23] Z. Dvořák, D. Král, R. Thomas, “Testing first-order properties for subclasses of sparse graphs”, J. ACM, 60:5 (2013), Art. 36, 24 pp. | DOI | MR | Zbl

[24] Z. Dvořák, S. Norine, “Small graph classes and bounded expansion”, J. Combin. Theory Ser. B, 100:2 (2010), 171–175 | DOI | MR | Zbl

[25] L. C. Eggan, “Transition graphs and the star-height of regular events”, Michigan Math. J., 10:4 (1963), 385–397 | DOI | MR | Zbl

[26] G. Elek, Convergence and limits of linear representations of finite groups, 2014 (v5 – 2015), 31 pp., arXiv: 1406.5032v4

[27] G. Elek, B. Szegedy, Limits of hypergraphs, removal and regularity lemmas. A non-standard approach, 2007, 25 pp., arXiv: 0705.2179v1

[28] F. Fiorenzi, P. Ochem, P. Ossona de Mendez, X. Zhu, “Thue choosability of trees”, Discrete Appl. Math., 159:17 (2011), 2045–2049 | DOI | MR | Zbl

[29] F. V. Fomin, D. Lokshtanov, S. Saurabh, D. M. Thilikos, “Bidimensionality and kernels”, SODA' 10 Proceedings of the 21st annual ACM–SIAM symposium on discrete algorithms, SIAM, Philadelphia, PA, 2010, 503–510 | DOI | MR | Zbl

[30] F. V. Fomin, D. Lokshtanov, S. Saurabh, D. M. Thilikos, “Linear kernels for (connected) dominating set on $H$-minor-free graphs”, SODA' 12 Proceedings of the 23rd annual ACM–SIAM symposium on discrete algorithms, ACM, New York, 2012, 82–92 | MR

[31] F. V. Fomin, D. Lokshtanov, S. Saurabh, D. M. Thilikos, “Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs”, STACS 2013 30th International symposium on theoretical aspects of computer science, LIPIcs. Leibniz Int. Proc. Inform., 20, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2013, 92–103 | MR

[32] H. M. Friedman, Addendum to “On the logic of measure and category I”, Ohio State Univ., 1979, Manuscript

[33] W. T. Gowers, “Lower bounds of tower type for Szemerédi's uniformity lemma”, Geom. Funct. Anal., 7:2 (1997), 322–337 | DOI | MR | Zbl

[34] M. Grohe, S. Kreutzer, S. Siebertz, Deciding first-order properties of nowhere dense graphs, 2013 (v2 – 2014), 30 pp., arXiv: 1311.3899v1

[35] H. Hatami, S. Norine, “The entropy of random-free graphons and properties”, Combin. Probab. Comput., 22:4 (2013), 517–526 ; (2012), 7 pp., arXiv: 1205.3529 | DOI | MR | Zbl

[36] D. Haussler, E. Welzl, “$\varepsilon$-nets and simplex range queries”, Discrete Comput. Geom., 2:2 (1987), 127–151 | DOI | MR | Zbl

[37] G. Hjorth, A. Nies, “Borel structures and {B}orel theories”, J. Symbolic Logic, 76:2 (2011), 461–476 | DOI | MR | Zbl

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

[39] S. Janson, “Graph limits and hereditary properties”, European J. Combin., 52, part B (2016), 321–337 ; (2011 (v3 – 2013)), 8 pp., arXiv: 1102.3571v1 | DOI | MR | Zbl

[40] S. Janson, Graphons, cut norm and distance, couplings and rearrangements, NYJM Monogr., 4, State Univ. of New York, Univ. at Albany, Albany, NY, 2013, 76 pp. | MR | Zbl

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

[42] W. Kazana, L. Segoufin, “Enumeration of first-order queries on classes of structures with bounded expansion”, PODS' 13 Proceedings of the 32nd symposium on principles of database systems, ACM, New York, NY, 2013, 297–308 | DOI

[43] H. A. Kierstead, D. Yang, “Orderings on graphs and game coloring number”, Order, 20:3 (2003), 255–264 | DOI | MR | Zbl

[44] M. C. Laskowski, “Vapnik–Chervonenkis classes of definable sets”, J. London Math. Soc. (2), 45:2 (1992), 377–384 | DOI | MR | Zbl

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

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

[47] L. Lovász, B. Szegedy, “Regularity partitions and the topology of graphons”, An irregular mind. Szemerédi is 70, Bolyai Soc. Math. Stud., 21, J. Bolyai Math. Soc., Budapest, 2010, 415–446 | DOI | MR | Zbl

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

[49] J. Nešetřil, P. Ossona de Mendez, “Colorings and homomorphisms of minor closed classes”, Discrete and computational geometry, Algorithms Combin., 25, Springer, Berlin, 2003, 651–664 | DOI | MR | Zbl

[50] J. Nešetřil, P. Ossona de Mendez, “The grad of a graph and classes with bounded expansion”, 7th International colloquium on graph theory, Electron. Notes Discrete Math., 22, Elsevier Science B.V., Amsterdam, 2005, 101–106 (electronic) | DOI | MR | Zbl

[51] J. Nešetřil, P. 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, NY, 2006, 391–400 | DOI | MR | Zbl

[52] J. Nešetřil, P. Ossona de Mendez, “Tree-depth, subgraph coloring and homomorphism bounds”, European J. Combin., 27:6 (2006), 1022–1041 | DOI | MR | Zbl

[53] J. Nešetřil, P. Ossona de Mendez, “Grad and classes with bounded expansion. I. Decompositions”, European J. Combin., 29:3 (2008), 760–776 | DOI | MR | Zbl

[54] J. Nešetřil, P. Ossona de Mendez, “Grad and classes with bounded expansion. II. Algorithmic aspects”, European J. Combin., 29:3 (2008), 777–791 | DOI | MR | Zbl

[55] J. Nešetřil, P. Ossona de Mendez, “First order properties on nowhere dense structures”, J. Symbolic Logic, 75:3 (2010), 868–887 | DOI | MR | Zbl

[56] J. Nešetřil, P. Ossona de Mendez, “From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits”, European congress of mathematics (Amsterdam, 2008), Eur. Math. Soc., Zürich, 2010, 135–165 | DOI | MR | Zbl

[57] J. Nešetřil, P. Ossona de Mendez, “Sparse combinatorial structures: classification and applications”, Proceedings of the International congress of mathematicians 2010 (ICM 2010) (Hyderabad, India), v. IV, Hindustan Book Agency, New Delhi, 2011, 2502–2529 | DOI | MR | Zbl

[58] J. Nešetřil, P. Ossona de Mendez, “How many $F$'s are there in $G$?”, European J. Combin., 32:7 (2011), 1126–1141 | DOI | MR | Zbl

[59] J. Nešetřil, P. Ossona de Mendez, “On nowhere dense graphs”, European J. Combin., 32:4 (2011), 600–617 | DOI | MR | Zbl

[60] J. Nešetřil, P. Ossona de Mendez, “A model theory approach to structural limits”, Comment. Math. Univ. Carolin., 53:4 (2012), 581–603 | MR | Zbl

[61] J. Nešetřil, P. Ossona de Mendez, Sparsity. Graphs, structures, and algorithms, Algorithms Combin., 28, Springer, Heidelberg, 2012, xxiv+457 pp. | DOI | MR | Zbl

[62] J. Nešetřil, P. Ossona de Mendez, Modeling limits in hereditary classes: reduction and application to trees, 2013, 26 pp., arXiv: 1312.0441

[63] J. Nešetřil, P. Ossona de Mendez, A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth), 2013, 95 pp., arXiv: 1303.6471v1

[64] J. Nešetřil, P. Ossona de Mendez, On low tree-depth decompositions, 2014, 20 pp., arXiv: 1412.1581v1

[65] J. Nešetřil, S. Poljak, “On the complexity of the subgraph problem”, Comment. Math. Univ. Carolin., 26:2 (1985), 415–419 | MR | Zbl

[66] J. Nešetřil, S. Shelah, “On the order of countable graphs”, European J. Combin., 24:6 (2003), 649–663 | DOI | MR | Zbl

[67] S. Plotkin, S. Rao, W. D. Smith, “Shallow excluded minors and improved graph decompositions”, Proceedings of the 5th annual ACM–SIAM symposium on discrete algorithms (Arlington, VA, 1994), ACM, New York, NY, 1994, 462–470 | MR | Zbl

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

[69] B. Rossman, “Homomorphism preservation theorems”, J. ACM, 55:3 (2008), Art. 15, 53 pp. | DOI | MR | Zbl

[70] N. Sauer, “On the density of families of sets”, J. Combinatorial Theory Ser. A, 13:1 (1972), 145–147 | DOI | MR | Zbl

[71] A. A. Schäffer, “Optimal node ranking of trees in linear time”, Inform. Process. Lett., 33:2 (1989), 91–96 | DOI | MR | Zbl

[72] S. Shelah, “Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory”, Ann. Math. Logic, 3:3 (1971), 271–362 | DOI | MR | Zbl

[73] S. Shelah, Classification theory and the number of non-isomorphic models, Stud. Logic Found. Math., 92, 2nd ed., North-Holland Publishing Co., Amsterdam, 1990, xxxiv+705 pp. | MR | Zbl

[74] C. I. Steinhorn, “Borel structures and measure and category logics”, Model-theoretic logics, Perspect. Math. Logic, Springer, New York, 1985, 579–596 | MR | Zbl

[75] E. Szemerédi, “Regular partitions of graphs”, Problèmes combinatoires et théorie des graphes (Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, 260, CNRS, Paris, 1978, 399–401 | MR | Zbl

[76] V. N. Vapnik, A. Y. Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities”, Theory Probab. Appl., 16:2 (1971), 264–280 | DOI | MR | Zbl

[77] A. M. Vershik, “Random metric spaces and universality”, Russian Math. Surveys, 59:2 (2004), 259–295 | DOI | DOI | MR | Zbl

[78] X. Zhu, “Colouring graphs with bounded generalized colouring number”, Discrete Math., 309:18 (2009), 5562–5568 | DOI | MR | Zbl