Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-29T09:36:07.839Z Has data issue: false hasContentIssue false
  • English
  • Français

Universal and unavoidable graphs

Part of: Graph theory Extremal combinatorics

Published online by Cambridge University Press:  15 April 2021

Matija Bucić ,
Nemanja Draganić  and
Benny Sudakov
Matija Bucić
Affiliation:
Department of Mathematics, ETH, Zürich, Switzerland
Nemanja Draganić
Affiliation:
Department of Mathematics, ETH, Zürich, Switzerland
Benny Sudakov*
Affiliation:
Department of Mathematics, ETH, Zürich, Switzerland
*
*Corresponding author. Email: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The Turán number ex(n, H) of a graph H is the maximal number of edges in an H-free graph on n vertices. In 1983, Chung and Erdős asked which graphs H with e edges minimise ex(n, H). They resolved this question asymptotically for most of the range of e and asked to complete the picture. In this paper, we answer their question by resolving all remaining cases. Our result translates directly to the setting of universality, a well-studied notion of finding graphs which contain every graph belonging to a certain family. In this setting, we extend previous work done by Babai, Chung, Erdős, Graham and Spencer, and by Alon and Asodi.

MSC classification

Primary: 05C80: Random graphs
Secondary: 05C60: Isomorphism problems (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) 05D40: Probabilistic methods 05C35: Extremal problems
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 30 , Issue 6 , November 2021 , pp. 942 - 955
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Footnotes

†

Research supported in part by SNSF grant 200021_196965.

References

Alon, N. and Asodi, V. (2002) Sparse universal graphs. J. Comput. Appl. Math. 142(1) 1–11.CrossRefGoogle Scholar
Alon, N. and Capalbo, M. (2007) Sparse universal graphs for bounded-degree graphs. Random Struct. Algorithms 31(2) 123–133.CrossRefGoogle Scholar
Alon, N. and Capalbo, M. (2008) Optimal universal graphs with deterministic embedding. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, pp. 373–378.Google Scholar
Alon, N., Krivelevich, M. and Sudakov, B. (2007) Embedding nearly-spanning bounded degree trees. Combinatorica 27(6) 629–644.CrossRefGoogle Scholar
Babai, L., Chung, F. R. K., Erdős, P., Graham, R. L. and Spencer, J. H. (1982) On graphs which contain all sparse graphs. In Theory and Practice of Combinatorics, Vol. 60 of North-Holland Mathematics Studies, pp. 21–26.CrossRefGoogle Scholar
Bhatt, S. N., Chung, F. R. K., Leighton, F. T. and Rosenberg, A. L. (1989) Universal graphs for bounded-degree trees and planar graphs. SIAM J. Discrete Math. 2(2) 145–155.CrossRefGoogle Scholar
Bollobás, B. and Erdős, P. (1973) On the structure of edge graphs. Bull. London Math. Soc. 5 317–321.CrossRefGoogle Scholar
Chung, F. R. K. (1983) Unavoidable stars in 3-graphs. J. Combin. Theory Ser. A 35(3) 252–262.CrossRefGoogle Scholar
Chung, F. R. K. (1997) Open problems of Paul Erdős in graph theory. J. Graph Theory 25(1) 3–36.3.0.CO;2-R>CrossRefGoogle Scholar
Chung, F. R. K. and Erdős, P. (1983) On unavoidable graphs. Combinatorica 3(2) 167–176.CrossRefGoogle Scholar
Chung, F. R. K. and Erdős, P. (1987) On unavoidable hypergraphs. J. Graph Theory 11(2) 251–263.CrossRefGoogle Scholar
Chung, F. R. K., Erdős, P. and Graham, R. L. (1981) Minimal decompositions of graphs into mutually isomorphic subgraphs. Combinatorica 1(1) 13–24.CrossRefGoogle Scholar
Chung, F. R. K. and Graham, R. L. (1979) On universal graphs. Ann. New York Acad. Sci. 319 136–140.CrossRefGoogle Scholar
Chung, F. R. K. and Graham, R. L. (1983) On universal graphs for spanning trees. J. London Math. Soc. (2) 27(2) 203–211.CrossRefGoogle Scholar
Chvátal, V. and Szemerédi, E. (1981) On the Erdős-Stone theorem. J. London Math. Soc. (2) 2 207–214.CrossRefGoogle Scholar
Conlon, D., Ferber, A., Nenadov, R. and Škorić, N. (2017) Almost-spanning universality in random graphs. Random Struct. Algorithms 50(3) 380–393.CrossRefGoogle Scholar
Duke, R. A. and Erdős, P. (1977) Systems of finite sets having a common intersection. In Proceedings. 8th SE Conference on Combinatorics, Graph Theory and Computing, pp. 247–252.Google Scholar
Erdős, P. and Simonovits, M. (1966) A limit theorem in graph theory. Studia Sci. Math. Hungar. 1 51–57.Google Scholar
Erdős, P. and Stone, A. H. (1946) On the structure of linear graphs. Bull. Amer. Math. Soc. 52 1087–1091.CrossRefGoogle Scholar
Füredi, Z. (1991) Turán type problems. In Surveys in Combinatorics, (Guildford, 1991), Vol. 166, London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, pp. 253–300.CrossRefGoogle Scholar
Füredi, Z. and Simonovits, M. (2013) The history of degenerate (bipartite) extremal graph problems. In Erdős Centennial, Vol. 25 of Bolyai Society Mathematical Studies, János Bolyai Mathematical Society, Budapest, pp. 169–264.CrossRefGoogle Scholar
Hetterich, S., Parczyk, O. and Person, Y. (2016) On universal hypergraphs. Electron. J. Combin. 23(4) P4.28.CrossRefGoogle Scholar
Keevash, P. (2011) Hypergraph Turán problems. In Surveys in Combinatorics 2011, London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, pp. 83–139.CrossRefGoogle Scholar
Montgomery, R. (2019) Spanning trees in random graphs. Adv. Math. 356 1–92.CrossRefGoogle Scholar
Sidorenko, A. (1995) What we know and what we do not know about Turán numbers. Graphs Comb. 11(2) 179–199.CrossRefGoogle Scholar
Sudakov, B. (2010) Recent developments in extremal combinatorics: Ramsey and Turán type problems. In Proceedings of the International Congress of Mathematicians, Volume IV, Hindustan Book Agency, New Delhi, pp. 2579–2606.Google Scholar
Turán, P. (1941) On an extremal problem in graph theory. Mat. Fiz. Lapok 48 436–452.Google Scholar