Beyond the $C_4$ extremal number: must a graph contain $\gg n^{1/2}$ four-cycles? (Erdős #60)
Statement
Let $\mathrm{ex}(n;C_4)$ denote the maximum number of edges in a graph on $n$ vertices containing no cycle of length $4$. Does every graph on $n$ vertices with more than $\mathrm{ex}(n;C_4)$ edges contain $\gg n^{1/2}$ many copies of $C_4$? That is, is there an absolute constant $c>0$ such that every $n$-vertex graph with at least $\mathrm{ex}(n;C_4)+1$ edges contains at least $c\,n^{1/2}$ four-cycles?
Acceptance. FULLY RESOLVES: a proof that there is an absolute constant $c>0$ such that for all sufficiently large $n$, every $n$-vertex graph with more than $\mathrm{ex}(n;C_4)$ edges contains at least $c\,n^{1/2}$ copies of $C_4$ — machine-checkable (Lean/Coq) preferred, else a complete written proof; OR a disproof: an explicit infinite family of graphs, one for infinitely many $n$, each with more than $\mathrm{ex}(n;C_4)$ edges but $o(n^{1/2})$ four-cycles, with a proof of both properties (finite examples alone cannot settle the asymptotic claim). ADVANCES: prove any lower bound on the guaranteed number of $C_4$'s that tends to infinity with $n$; prove the currently-open '≥2 copies' statement for all large $n$; extend the He–Ma–Yang result beyond $n=q^2+q+1$ with $q$ even, strictly enlarging the set of $n$ covered as stated in the background; or a reproducible exhaustive computation of the minimum number of $C_4$'s among $n$-vertex graphs with $\mathrm{ex}(n;C_4)+1$ edges for all $n$ up to a stated bound (code + exhaustiveness certificate — new data not recorded in the cited literature). Deliver the proof file, or the enumeration code plus verified tables.
Background
Conjectured by Erdős and Simonovits; recorded by Erdős in [Er90] and [Er93, p.335], and listed as open on erdosproblems.com/60 (fetched 2026-07-13, status 'open', tagged 'graph theory | cycles'). Strikingly, Erdős and Simonovits could not even prove that exceeding the extremal number forces at least TWO copies of $C_4$ — so even the very first step beyond the trivial one copy is open in general. He, Ma, and Yang [HeMaYa21] proved the conjecture when $n=q^2+q+1$ for an even integer $q$ — the regime where the extremal $C_4$-free graphs are governed by polarity graphs of projective planes of order $q$. Context on the extremal function itself: classical work (the Kővári–Sós–Turán upper bound and the Erdős–Rényi–Sós/Brown polarity-graph constructions) gives $\mathrm{ex}(n;C_4)=(\tfrac{1}{2}+o(1))n^{3/2}$, and Füredi determined it exactly for $n=q^2+q+1$ with $q>13$ a prime power; the finer behaviour of $\mathrm{ex}(n;C_4)$ is itself Erdős #765 (erdosproblems.com/765). OEIS A006855 records the exact values of $\mathrm{ex}(n;C_4)$ for small $n$. The conjectured count $n^{1/2}\approx q$ matches the intuition that adding one edge to a polarity graph should create roughly $q$ four-cycles. The attacker's tools: supersaturation and stability methods around the polarity-graph extremal structure on the proof side; computationally, exhaustive determination of the minimum $C_4$-count among $n$-vertex graphs with $\mathrm{ex}(n;C_4)+1$ edges for small $n$ (extending the known exact extremal data), which would give the first systematic evidence table, test the '≥2 copies' sub-question, and probe irregular values of $n$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #60 (T. F. Bloom) | website |
| REF-02 | OEIS A006855 — maximal number of edges in an n-vertex squarefree (C_4-free) graph | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.