Universal and unavoidable graphs

Matija Bucić, Nemanja Draganić, Benny Sudakov

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Article number21000110
JournalCombinatorics Probability and Computing
StateAccepted/In press - 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


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

Cite this