Unavoidable Hypergraphs

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

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

The following very natural problem was raised by Chung and Erdős in the early 80’s. 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)
Title of host publicationTrends in Mathematics
PublisherSpringer Science and Business Media Deutschland GmbH
Pages339-344
Number of pages6
DOIs
StatePublished - 2021
Externally publishedYes

Publication series

NameTrends in Mathematics
Volume14
ISSN (Print)2297-0215
ISSN (Electronic)2297-024X

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • Hypergraphs
  • Turán numbers
  • Unavoidable graphs

Fingerprint

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

Cite this