The number of -free graphs
In the authors' words
Erd\H{o}s, Frankl and R\"odl showed that the number of graphs on vertices with no copy of a non-bipartite graph is , whereas Morris and Saxton showed that this fails for . Answering a question of Erd\H{o}s, we prove that the number of -free graphs on vertices is . The proof combines a modified hypergraph container method that treats pairs of vertices with large codegree separately, with a new bound on the number of matchings in a graph.
Main resultThe abstract does not state a limitation.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 14 pages