{"id":"arxiv/2610.39595","url":"https://arxiv.org/abs/2610.39595","tags":["math.CO"],"score":0,"title":"The number of $C_4$-free graphs","domain":"math.CO","source":"arxiv","authors":["Tianchi Yang"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}