The missing factor in counting C4-free graphs is closed: the count on n vertices lands at exponent 3/2

The number of four-cycle-free graphs on n vertices is pinned to the scale $2^{O(n^{3/2})}$, the form Erdős's question asks for. The earlier Kleitman–Winston bound left a constant-factor gap in the exponent, and Balogh and Samotij showed almost all four-cycle-free graphs have at most a fixed constant times $n^{3/2}$ edges, but the count itself was not closed. The result is stated as a theorem and matches the exponent of the $2^{\Omega(n^{3/2})}$ lower bound; for non-bipartite graphs Erdős, Frankl and Rödl proved the analogous estimate, while Morris and Saxton showed it fails for some bipartite graphs containing a cycle, so the four-cycle case needed separate treatment.

The proof restricts the container method to four-cycles whose two diagonals both have small codegree, and leaves the remaining four-cycles to be counted inside each container. The standard route hands all four-cycles to the container method at once, but a container can still hold many four-cycles with a high-codegree diagonal, so its subgraphs cannot be counted directly. High-degree vertices and edges that push the diagonal graph past a degree limit are deleted first, then the Saxton–Thomason container theorem is applied to the remaining four-cycles, giving at most $2^{O(n^{3/2})}$ containers that cover every four-cycle-free graph.

Counting inside a container splits into a record of common neighbors plus a matching in an auxiliary graph. After each neighborhood is cut into connected pieces of bounded size and vertices are split accordingly, a four-cycle-free subgraph is determined by that record together with a matching, so the count reduces to bounding records and matchings separately. Records are bounded directly, and matchings are controlled by a new proposition giving an upper bound of the form $2^{e(G)/2}$ up to constants for every graph, a constant already attained on a single edge and matching the constant in the final theorem.

The result concerns the fixed four-cycle specifically and gives a $2^{O(n^{3/2})}$ upper bound on the number of four-cycle-free graphs on n vertices, with the same exponent as the known lower bound; the intended readers are researchers in extremal combinatorics and graph enumeration.

The constant in the matching bound is already attained on a single edge, so that step has no room to tighten; the text does not say whether deferring diagonals extends to other bipartite graphs containing a cycle.