We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Supersaturated Sparse Graphs and Hypergraphs.
- Authors
Ferber, Asaf; McKinley, Gweneth; Samotij, Wojciech
- Abstract
A central problem in extremal graph theory is to estimate, for a given graph H , the number of H -free graphs on a given set of n vertices. In the case when H is not bipartite, Erd̋s, Frankl, and Rödl proved that there are 2(1+ o (1))ex(n , H) such graphs. In the bipartite case, however, bounds of the form 2 O (ex(n , H)) have been proven only for relatively few special graphs H. As a 1st attempt at addressing this problem in full generality, we show that such a bound follows merely from a rather natural assumption on the growth rate of n ↦ ex(n , H); an analogous statement remains true when H is a uniform hypergraph. Subsequently, we derive several new results, along with most previously known estimates, as simple corollaries of our theorem. At the heart of our proof lies a general supersaturation statement that extends the seminal work of Erd̋s and Simonovits. The bounds on the number of H -free hypergraphs are derived from it using the method of hypergraph containers.
- Subjects
HYPERGRAPHS; SPARSE graphs; EXTREMAL problems (Mathematics)
- Publication
IMRN: International Mathematics Research Notices, 2020, Vol 2020, Issue 2, p378
- ISSN
1073-7928
- Publication type
Article
- DOI
10.1093/imrn/rny030