×

Graph theory – a survey on the occasion of the Abel Prize for László Lovász. (English) Zbl 1492.01017

Summary: In this survey, we explain a few key ideas of the theory of graphs, and how these ideas have grown to form the foundation of entire research areas. Graph Theory is a fairly young mathematical discipline; here we explain some of its major challenges for the 21st century.
László Lovász was recently awarded the Abel Prize. He made important contributions to all the areas discussed in this survey, and we close by summarising his main achievements.

MSC:

01A70 Biographies, obituaries, personalia, bibliographies
05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05Cxx Graph theory

Biographic References:

Lovász, László
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ackermann, W., Die widerspruchsfreiheit der allgemeinen mengenlehre, Math. Ann., 114, 1, 305-315 (1937) · Zbl 0016.19501 · doi:10.1007/BF01594179
[2] Aharoni, R., Ryser’s conjecture for tripartite 3-graphs, Combinatorica, 21, 1, 1-4 (2001) · Zbl 1107.05307 · doi:10.1007/s004930170001
[3] Aharoni, R.; Berger, E., The intersection of a matroid and a simplicial complex, Trans. Am. Math. Soc., 358, 11, 4895-4917 (2006) · Zbl 1108.05023 · doi:10.1090/S0002-9947-06-03833-5
[4] Aharoni, R.; Berger, E., Menger’s theorem for infinite graphs, Invent. Math., 176, 1-62 (2009) · Zbl 1216.05092 · doi:10.1007/s00222-008-0157-3
[5] Ajtai, M.; Komlós, J.; Szemerédi, E., A note on Ramsey numbers, J. Comb. Theory, Ser. A, 29, 3, 354-360 (1980) · Zbl 0455.05045 · doi:10.1016/0097-3165(80)90030-8
[6] Aldous, D.; Lyons, R., Processes on unimodular random networks, Electron. J. Probab., 12, 1454-1508 (2007) · Zbl 1131.60003 · doi:10.1214/EJP.v12-463
[7] Attila, J., Proof of Nash-Williams’ intersection conjecture for countable matroids, Adv. Math., 380 (2021) · Zbl 1458.05038 · doi:10.1016/j.aim.2021.107608
[8] Babson, E., Kozlov, D.N.: Proof of the Lovász conjecture. Ann. Math., 965-1007 (2007) · Zbl 1132.05019
[9] Bohman, T.; Keevash, P., The early evolution of the h-free process, Invent. Math., 181, 2, 291-336 (2010) · Zbl 1223.05270 · doi:10.1007/s00222-010-0247-x
[10] Bowler, N.; Carmesin, J., Matroid intersection, base packing and base covering for infinite matroids, Combinatorica, 35, 2, 153-180 (2015) · Zbl 1349.05051 · doi:10.1007/s00493-014-2953-2
[11] Bruhn, H.; Diestel, R.; Kriesell, M.; Pendavingh, R.; Wollan, P., Axioms for infinite matroids, Adv. Math., 239, 18-46 (2013) · Zbl 1279.05013 · doi:10.1016/j.aim.2013.01.011
[12] Bucić, M.; Kwan, M.; Pokrovskiy, A.; Sudakov, B., Halfway to rota’s basis conjecture, Int. Math. Res. Not., 2020, 21, 8007-8026 (2020) · Zbl 1465.05026 · doi:10.1093/imrn/rnaa004
[13] Carmesin, J.: Embedding simply connected 2-complexes in 3-space - V. A refined Kuratowski-type characterisation. Preprint 2017. Available at https://arxiv.org/pdf/1709.04659.pdf
[14] Carmesin, J.: Local 2-separators. Preprint. Available at http://web.mat.bham.ac.uk/J.Carmesin/
[15] Chekuri, C.; Chuzhoy, J., Polynomial bounds for the grid-minor theorem, J. ACM, 63, 5, 40 (2016) · Zbl 1410.05186 · doi:10.1145/2820609
[16] Chudnovsky, M., The Erdös-Hajnal conjecture – a survey, J. Graph Theory, 75, 2, 178-190 (2014) · Zbl 1280.05086 · doi:10.1002/jgt.21730
[17] Chudnovsky, M.; Cornuéjols, G.; Liu, X.; Seymour, P.; Vušković, K., Recognizing Berge graphs, Combinatorica, 25, 143-186 (2005) · Zbl 1089.05027 · doi:10.1007/s00493-005-0012-8
[18] Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math., 51-229 (2006) · Zbl 1112.05042
[19] Chudnovsky, M.; Lagoutte, A.; Seymour, P.; Spirkl, S., Colouring perfect graphs with bounded clique number, J. Comb. Theory, Ser. B, 122, 757-775 (2017) · Zbl 1350.05030 · doi:10.1016/j.jctb.2016.09.006
[20] Chuzhoy, J.; Tan, Z., Towards tight(er) bounds for the excluded grid theorem, J. Comb. Theory, Ser. B, 146, 219-265 (2021) · Zbl 1457.05104 · doi:10.1016/j.jctb.2020.09.010
[21] Conlon, D.: A new upper bound for diagonal Ramsey numbers. Ann. Math., 941-960 (2009) · Zbl 1188.05087
[22] Conlon, D., Gowers, W.T.: Combinatorial theorems in sparse random sets. Ann. Math., 367-454 (2016) · Zbl 1351.05204
[23] Cooper, J. W.; Král’, D.; Martins, T. L., Finitely forcible graph limits are universal, Adv. Math., 340, 819-854 (2018) · Zbl 1400.05124 · doi:10.1016/j.aim.2018.10.019
[24] Diestel, R., Graph Theory (2017), Berlin: Springer, Berlin · Zbl 1375.05002 · doi:10.1007/978-3-662-53622-3
[25] Diestel, R., Abstract separation systems, Order, 35, 1, 157-170 (2018) · Zbl 1469.06006 · doi:10.1007/s11083-017-9424-5
[26] Diestel, R.: Tangles in the social sciences. arXiv preprint. 1907.07341 (2019)
[27] Diestel, R., Oum, S.-i.: Tangle-tree duality in abstract separation systems. Adv. Math., 107470 (2020) · Zbl 1471.05087
[28] Diestel, R.; Jensen, T. R.; Gorbunov, K. Yu.; Thomassen, C., Highly connected sets and the excluded grid theorem, J. Comb. Theory, Ser. B, 75, 1, 61-73 (1999) · Zbl 0949.05075 · doi:10.1006/jctb.1998.1862
[29] Elbracht, C., Fioravanti, D., Klepper, S., Kneip, J., Rendsburg, L., Teegen, M., von Luxburg, U.: Tangles: from weak to strong clustering. arXiv preprint. arXiv:2006.14444 (2020)
[30] Erdos, P.; Rényi, A., Asymmetric graphs, Acta Math. Acad. Sci. Hung., 14, 295-315, 15 (1963) · Zbl 0118.18901
[31] Freudenthal, H., Neuaufbau der Endentheorie, Ann. Math., 43, 261-279 (1942) · Zbl 0060.40006 · doi:10.2307/1968869
[32] Geelen, J.; Nelson, P., On minor-closed classes of matroids with exponential growth rate, Adv. Appl. Math., 50, 1, 142-154 (2013) · Zbl 1310.05046 · doi:10.1016/j.aam.2012.03.004
[33] Geelen, J.; Nelson, P., The densest matroids in minor-closed classes with exponential growth rate, Trans. Am. Math. Soc., 369, 9, 6751-6776 (2017) · Zbl 1365.05041 · doi:10.1090/tran/7186
[34] Geelen, J.; Oum, S.-i., Circle graph obstructions under pivoting, J. Graph Theory, 61, 1, 1-11 (2009) · Zbl 1207.05189 · doi:10.1002/jgt.20363
[35] Geelen, J.; Gerards, B.; Whittle, G., Solving Rota’s conjecture, Not. Am. Math. Soc., 61, 7, 736-743 (2014) · Zbl 1338.05039 · doi:10.1090/noti1139
[36] Giannopoulou, A. C.; Kawarabayashi, K.-i.; Kreutzer, S.; Kwon, O.-j., The directed flat wall theorem, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 239-258 (2020), Philadelphia: SIAM, Philadelphia · Zbl 07304038 · doi:10.1137/1.9781611975994.15
[37] Glock, S.; Kühn, D.; Lo, A.; Montgomery, R.; Osthus, D., On the decomposition threshold of a given graph, J. Comb. Theory, Ser. B, 139, 47-127 (2019) · Zbl 1428.05246 · doi:10.1016/j.jctb.2019.02.010
[38] Gromov, M., Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc., 1, 2, 109-197 (1999) · Zbl 0998.14001 · doi:10.1007/PL00011162
[39] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (2012), Berlin: Springer, Berlin · Zbl 0837.05001
[40] Grzesik, A.; Král, D.; Lovász, L. M., Elusive extremal graphs, Proc. Lond. Math. Soc., 121, 6, 1685-1736 (2020) · Zbl 1462.05194 · doi:10.1112/plms.12382
[41] Gustavsson, T.: Decompositions of large graphs and digraphs with high minimum degree. PhD thesis, Univ. (1991)
[42] Hatami, H.; Lovász, L.; Szegedy, B., Limits of locally-globally convergent graph sequences, Geom. Funct. Anal., 24, 1, 269-296 (2014) · Zbl 1294.05109 · doi:10.1007/s00039-014-0258-7
[43] He, Z.-X.; Schramm, O., Hyperbolic and parabolic packings, Discrete Comput. Geom., 14, 2, 123-149 (1995) · Zbl 0830.52010 · doi:10.1007/BF02570699
[44] He, Z.-X.; Schramm, O., On the convergence of circle packings to the Riemann map, Invent. Math., 125, 2, 285-305 (1996) · Zbl 0868.30010 · doi:10.1007/s002220050076
[45] Hopcroft, J.; Tarjan, R., Efficient planarity testing, J. ACM, 21, 4, 549-568 (1974) · Zbl 0307.68025 · doi:10.1145/321850.321852
[46] Kawarabayashi, K.-i.; Mohar, B.; Reed, B., A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width, 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 771-780 (2008) · doi:10.1109/FOCS.2008.53
[47] Keevash, P.: The existence of designs. arXiv preprint. 1401.3665 (2014)
[48] Kim, R.; Kwon, O.-j.; Oum, S.-i.; Sivaraman, V., Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi \)-bounded, J. Comb. Theory, Ser. B, 140, 372-386 (2020) · Zbl 1430.05058 · doi:10.1016/j.jctb.2019.06.001
[49] Kozlov, D., Combinatorial Algebraic Topology (2008), Berlin: Springer, Berlin · Zbl 1130.55001 · doi:10.1007/978-3-540-71962-5
[50] Kunszenti-Kovács, D.; Lovász, L.; Szegedy, B., Measures on the square as sparse graph limits, J. Comb. Theory, Ser. B, 138, 1-40 (2019) · Zbl 1415.05099 · doi:10.1016/j.jctb.2019.01.004
[51] Kuratowski, K., Sur le probleme des courbes gauches en topologie, Fundam. Math., 15, 1, 271-283 (1930) · JFM 56.1141.03 · doi:10.4064/fm-15-1-271-283
[52] Lovász, L., Kneser’s conjecture, chromatic number, and homotopy, J. Comb. Theory, Ser. A, 25, 3, 319-324 (1978) · Zbl 0418.05028 · doi:10.1016/0097-3165(78)90022-5
[53] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 1, 1-7 (1979) · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985
[54] Lovász, L., Submodular functions and convexity, Mathematical Programming the State of the Art, 235-257 (1983), Berlin: Springer, Berlin · Zbl 0566.90060 · doi:10.1007/978-3-642-68874-4_10
[55] Lovász, L., Combinatorial Problems and Exercises (2007), Providence: Am. Math. Soc., Providence · Zbl 1120.05001
[56] Lovász, L., Large Networks and Graph Limits (2012), Providence: Am. Math. Soc., Providence · Zbl 1292.05001
[57] Lovász, L.; Plummer, M. D., Matching Theory (2009), Providence: Am. Math. Soc., Providence · Zbl 1175.05002
[58] Mehlhorn, K.; Mutzel, P., On the embedding phase of the hopcroft and Tarjan planarity testing algorithm, Algorithmica, 16, 2, 233-242 (1996) · Zbl 0854.68075 · doi:10.1007/BF01940648
[59] Menger, K., Zur allgemeinen Kurventheorie, Fundam. Math., 10, 1, 96-115 (1927) · JFM 53.0561.01 · doi:10.4064/fm-10-1-96-115
[60] de Mesmay, A.; Rieck, Y.; Sedgwick, E.; Tancer, M., Embeddability in R3 is NP-hard, J. ACM, 67, 4, 1-29 (2020) · Zbl 1491.68079 · doi:10.1145/3396593
[61] Mohar, B., A linear time algorithm for embedding graphs in an arbitrary surface, SIAM J. Discrete Math., 12, 1, 6-26 (1999) · Zbl 0931.05025 · doi:10.1137/S089548019529248X
[62] Moser, R. A., A constructive proof of the Lovász local lemma, Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, 343-350 (2009) · Zbl 1304.68079 · doi:10.1145/1536414.1536462
[63] Moser, R. A.; Tardos, G., A constructive proof of the general Lovász local lemma, J. ACM, 57, 2, 1-15 (2010) · Zbl 1300.60024 · doi:10.1145/1667053.1667060
[64] Nash-Williams, C. St. J.A., Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc., 1, 1, 445-450 (1961) · Zbl 0102.38805 · doi:10.1112/jlms/s1-36.1.445
[65] Nash-Williams, C. St. J.A., Decomposition of finite graphs into forests, J. Lond. Math. Soc., 1, 1, 12 (1964) · Zbl 0119.38805 · doi:10.1112/jlms/s1-39.1.12
[66] Nash-Williams, C.St.J.A.: An unsolved problem concerning decomposition of graphs into triangles combinatorial theory and its applications III. P. Erdös, P. Rényi and V.T. Sós (eds.) (1970)
[67] Negami, S., The spherical genus and virtually planar graphs, Discrete Math., 70, 2, 159-168 (1988) · Zbl 0656.05031 · doi:10.1016/0012-365X(88)90090-8
[68] Nešetřil, J.; Ossona de Mendez, P., Sparsity: Graphs, Structures, and Algorithms (2012), Berlin: Springer, Berlin · Zbl 1268.05002 · doi:10.1007/978-3-642-27875-4
[69] Oum, S.-i., Rank-width and vertex-minors, J. Comb. Theory, Ser. B, 95, 1, 79-100 (2005) · Zbl 1070.05023 · doi:10.1016/j.jctb.2005.03.003
[70] Oxley, J., Matroid Theory (2011), London: Oxford University Press, London · Zbl 1254.05002 · doi:10.1093/acprof:oso/9780198566946.001.0001
[71] Rado, R., Universal graphs and universal functions, Acta Arith., 9, 4, 331-340 (1964) · Zbl 0139.17303 · doi:10.4064/aa-9-4-331-340
[72] Ramsey, F. P., On a problem of formal logic, Proc. Lond. Math. Soc., 2, 1, 264-286 (1930) · JFM 55.0032.04 · doi:10.1112/plms/s2-30.1.264
[73] Razborov, A. A., Flag algebras, J. Symb. Log., 72, 4, 1239-1282 (2007) · Zbl 1146.03013 · doi:10.2178/jsl/1203350785
[74] Razborov, A. A., Flag algebras: an interim report, The Mathematics of Paul Erdős II, 207-232 (2013), Berlin: Springer, Berlin · doi:10.1007/978-1-4614-7254-4_16
[75] Reiher, C.: The clique density theorem. Ann. Math., 683-707 (2016) · Zbl 1348.05103
[76] Robertson, N.; Seymour, P. D., Graph minors. XX. Wagner’s conjecture, J. Comb. Theory, Ser. B, 92, 2, 325-357 (2004) · Zbl 1061.05088 · doi:10.1016/j.jctb.2004.08.001
[77] Robertson, N.; Seymour, P.; Thomas, R., Hadwiger’s conjecture for K6-free graphs, Combinatorica, 13, 3, 279-361 (1993) · Zbl 0830.05028 · doi:10.1007/BF01202354
[78] Rodin, B.; Sullivan, D., The convergence of circle packings to the Riemann mapping, J. Differ. Geom., 26, 2, 349-360 (1987) · Zbl 0694.30006 · doi:10.4310/jdg/1214441375
[79] Rubinstein, J. H., Problems around 3-manifolds, Workshop on Heegaard Splittings, 285-298 (2007) · Zbl 1139.57019
[80] Schacht, M.: Extremal results for random discrete structures. Ann. Math., 333-365 (2016) · Zbl 1351.05207
[81] Schleimer, S., Sphere recognition lies in np, Low-Dimensional and Symplectic Topology, 183-213 (2011) · Zbl 1250.57024 · doi:10.1090/pspum/082/2768660
[82] Schmidt, D. R.; Thomas, P. J., Measuring edge importance: a quantitative analysis of the stochastic shielding approximation for random processes on graphs, J. Math. Neurosci., 4, 1, 1-52 (2014) · Zbl 1291.92047 · doi:10.1186/2190-8567-4-6
[83] Scott, A.; Seymour, P., A survey of \(\chi \)-boundedness, J. Graph Theory, 95, 3, 473-504 (2020) · Zbl 1486.05102 · doi:10.1002/jgt.22601
[84] Serre, J.-P., Trees (1980), Berlin: Springer, Berlin · Zbl 0548.20018 · doi:10.1007/978-3-642-61856-7
[85] Seymour, P., Hadwiger’s conjecture, Open Problems in Mathematics, 417-437 (2016), Berlin: Springer, Berlin · Zbl 1347.05079 · doi:10.1007/978-3-319-32162-2_13
[86] Sidorenko, A., A correlation inequality for bipartite graphs, Graphs Comb., 9, 2, 201-204 (1993) · Zbl 0777.05096 · doi:10.1007/BF02988307
[87] Spencer, J., Ramsey’s theorem—a new lower bound, J. Comb. Theory, Ser. A, 18, 1, 108-115 (1975) · Zbl 0296.05003 · doi:10.1016/0097-3165(75)90071-0
[88] Stallings, J.R.: On torsion-free groups with infinitely many ends. Ann. Math., 312-334 (1968) · Zbl 0238.20036
[89] Thomassen, C., Every planar graph is 5-choosable, J. Comb. Theory, Ser. B, 62, 1, 180-181 (1994) · Zbl 0805.05023 · doi:10.1006/jctb.1994.1062
[90] Thompson, A., Thin position and the recognition problem for \(S^3\), Math. Res. Lett., 1, 5, 613-630 (1994) · Zbl 0849.57009 · doi:10.4310/MRL.1994.v1.n5.a9
[91] Tutte, W. T., Graph Theory as I Have Known It (1998), London: Oxford University Press, London · Zbl 0915.05041
[92] van der Holst, H., Graphs and obstructions in four dimensions, J. Comb. Theory, Ser. B, 96, 3, 388-404 (2006) · Zbl 1088.05067 · doi:10.1016/j.jctb.2005.09.004
[93] Van Der Holst, H.; Lovász, L.; Schrijver, A., The Colin de Verdiere graph parameter, Graph Theory and Computational Biology, 29-85 (1999) · Zbl 0930.05065
[94] Wagner, K., Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 114, 1, 570-590 (1937) · Zbl 0017.19005 · doi:10.1007/BF01594196
[95] Whitney, H., Non-separable and planar graphs, Trans. Am. Math. Soc., 34, 339-362 (1932) · Zbl 0004.13103 · doi:10.1090/S0002-9947-1932-1501641-2
[96] Wigderson, A., Mathematics and Computation (2019), Princeton: Princeton University Press, Princeton · Zbl 1455.68004 · doi:10.2307/j.ctvckq7xb
[97] Zentner, R., Integer homology 3-spheres admit irreducible representations in sl(2,c), Duke Math. J., 167, 9, 1643-1712 (2018) · Zbl 1407.57008 · doi:10.1215/00127094-2018-0004
[98] Ziegler, G. M., Generalized Kneser coloring theorems with combinatorial proofs, Invent. Math., 147, 3, 671-691 (2002) · Zbl 1029.05058 · doi:10.1007/s002220100188
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.