Unavoidable hypergraphs

The following very natural problem was raised by Chung and Erdős in the early 80's and has since been repeated a number of times. What is the minimum of the Turán number ex(n,H) among all r-graphs H with a fixed number of edges? Their actual focus was on an equivalent and perhaps even more natu...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 2021-11, Vol.151, p.307-338, Article 307
Main Authors: Bucić, Matija, Draganić, Nemanja, Sudakov, Benny, Tran, Tuan
Format: Article
Language:English
Subjects:
Hypergraph Turan numbers
Sunflowers
Unavoidable hypergraphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The following very natural problem was raised by Chung and Erdős in the early 80's and has since been repeated a number of times. What is the minimum of the Turán number ex(n,H) among all r-graphs H with a fixed number of edges? Their actual focus was on an equivalent and perhaps even more natural question which asks what is the largest size of an r-graph that can not be avoided in any r-graph on n vertices and e edges? In the original paper they resolve this question asymptotically for graphs, for most of the range of e. In a follow-up work Chung and Erdős resolve the 3-uniform case and raise the 4-uniform case as the natural next step. In this paper we make first progress on this problem in over 40 years by asymptotically resolving the 4-uniform case which gives us some indication on how the answer should behave in general.
ISSN:0095-8956
1096-0902
DOI:10.1016/j.jctb.2021.06.010