Universal and unavoidable graphs. (15th November 2021)

• Record Type: Journal Article
• Authors: Bucić, Matija; Draganić, Nemanja; Sudakov, Benny
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 6(2021)
• Page Start: 942
• Page End: 955
• Publication Date: 2021-11-15
• Subjects: 05C80 -- 05C60 -- 05D40 -- 05C35; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548321000110
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: 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.