Paperlane

no. 5 · Friday 30 October 2026

The number of $C_4$-free graphs

Tianchi Yang

math.CO · 14 pp

Abstract

Erdős, Frankl and Rödl showed that the number of graphs on $n$ vertices with no copy of a non-bipartite graph $H$ is $2^{(1+o(1))ex(n,H)}$, whereas Morris and Saxton showed that this fails for $C_6$. Answering a question of Erdős, we prove that the number of $C_4$-free graphs on $n$ vertices is $2^{(1+o(1))ex(n,C_4)}$. 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.

comments
14 pages
fields
Combinatorics
pdf ↗ page arXiv:2610.39595 ↗