Universal and unavoidable graphs

Matija Bucić; Nemanja Draganić; Benny Sudakov

doi:10.1017/S0963548321000110

Universal and unavoidable graphs

Matija Bucić, Nemanja Draganić, Benny Sudakov

Research output: Contribution to journal › Article › peer-review

3 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 language	English (US)
Pages (from-to)	942-955
Number of pages	14
Journal	Combinatorics Probability and Computing
Volume	30
Issue number	6
DOIs	https://doi.org/10.1017/S0963548321000110
State	Published - Nov 2021
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1017/S0963548321000110

Cite this

@article{8d16f1d8f9f04341a7279f695eb4eb12,

title = "Universal and unavoidable graphs",

abstract = "The Tur{\'a}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{\H o}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{\H o}s, Graham and Spencer, and by Alon and Asodi.",

author = "Matija Buci{\'c} and Nemanja Dragani{\'c} and Benny Sudakov",

note = "Publisher Copyright: {\textcopyright} The Author(s), 2021. Published by Cambridge University Press.",

year = "2021",

month = nov,

doi = "10.1017/S0963548321000110",

language = "English (US)",

volume = "30",

pages = "942--955",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "6",

}

TY - JOUR

T1 - Universal and unavoidable graphs

AU - Bucić, Matija

AU - Draganić, Nemanja

AU - Sudakov, Benny

N1 - Publisher Copyright: © The Author(s), 2021. Published by Cambridge University Press.

PY - 2021/11

Y1 - 2021/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85104520235&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85104520235&partnerID=8YFLogxK

U2 - 10.1017/S0963548321000110

DO - 10.1017/S0963548321000110

M3 - Article

AN - SCOPUS:85104520235

SN - 0963-5483

VL - 30

SP - 942

EP - 955

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 6

ER -

Universal and unavoidable graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this