The number of -free graphs
En palabras de los autores
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.
Resultado principalEl resumen no menciona limitaciones.
Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 14 pages