The number of $C_4$-free graphs
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 and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.39595
curl -X POST /api/v1/records/arxiv/2610.39595/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.39595/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'