Supersaturated Sparse Graphs and Hypergraphs. (8th March 2018)

• Record Type: Journal Article
• Authors: Ferber, Asaf; McKinley, Gweneth; Samotij, Wojciech
• Is Part Of: International mathematics research notices. Volume 2020:Number 2(2020)
• Page Start: 378
• Page End: 402
• Publication Date: 2018-03-08
• Subjects: Mathematics -- Periodicals; 510
• DOI: 10.1093/imrn/rny030
• Languages: English
• ISSNs: 1073-7928

Abstract

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.