math.CO — Combinatorics

Four-cycle supersaturation and polarity stability at $q^2+q$ vertices

Contributed by Zhenyu Sun

Let $m_0=\frac12q(q+1)^2-q$. For every even $q\ge1600$, we prove that a graph on $q^2+q$ vertices with at least $m_0+1$ edges contains at least $\lceil(q-1)/12\rceil$ four-cycles. For powers of two in this range, $m_0$ is the extremal number and a polarity construction has exactly $q-1$ four-cycles at $m_0+1$ edges. These bounds determine the order of magnitude of the minimum count on this sequence. We also prove a stability theorem: for every nonnegative integer $b$ and every even $q\ge10^{18}(b+1)^{16}$, each $C_4$-free graph on $q^2+q$ vertices with $m_0-b$ edges is a spanning subgraph of an orthogonal polarity graph with one point deleted. The required degree bounds follow from the edge count. As a consequence, a graph on $q^2+q$ vertices with $m_0+1$ edges has at least $q-1$ four-cycles if an edge set of size $t\ge1$ meets every four-cycle and $q$ is even with $q\ge10^{18}t^{16}$. The counting proof uses a codegree commutator; the stability proof combines degree-deficit concentration with incidence completion and polarity extension.

Author comments: 64 pages.