Unavoidable hypergraphs
OPEN ACCESS
Loading...
Author / Producer
Date
2021-11
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
© 2021 Elsevier Inc.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
151
Pages / Article No.
307 - 338
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Unavoidable hypergraphs; Hypergraph Turan numbers; Sunflowers
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
Notes
Funding
196965 - Problems in Extremal and Probabilistic Combinatorics (SNF)