Unavoidable hypergraphs

Matija Bucić, Nemanja Draganić, Benny Sudakov, Tuan Tran

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)307-338
Number of pages32
JournalJournal of Combinatorial Theory. Series B
Volume151
DOIs
StatePublished - Nov 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Hypergraph Turan numbers
  • Sunflowers
  • Unavoidable hypergraphs

Fingerprint

Dive into the research topics of 'Unavoidable hypergraphs'. Together they form a unique fingerprint.

Cite this