2017/10/12 by Ferber, Asaf, McKinley, Gweneth Anne, Samotij, Wojciech · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1710.04517
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, fairly precise estimates on this number are known. In particular, thirty years ago, Erdős, Frankl, and Rödl proved that there are 2(1+o(1))ex(n,H) such graphs. In the bipartite case, however, nontrivial bounds have been proven only for relatively few special graphs H. We make a first attempt at addressing this enumeration problem for a general bipartite graph H. We show that an upper bound of 2O(ex(n,H)) on the number of H-free graphs with n vertices 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.