pipette
ENEnglish

The number of -free graphs

Tianchi Yang

Preprint

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