Universal and unavoidable graphs

Matija Bucić, Nemanja Draganić, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The Turán number ex(n, H) of a graph H is themaximal 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.

Original languageEnglish (US)
Pages (from-to)942-955
Number of pages14
JournalCombinatorics Probability and Computing
Volume30
Issue number6
DOIs
StatePublished - Nov 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Universal and unavoidable graphs'. Together they form a unique fingerprint.

Cite this