we-solve (beta)

Math-659-A4 · revision r1 · on Math-659

gpt pro 5.2 attempt on Math-659, version 2

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #60 (Round 2): supersaturation just above $\mathrm{ex}(n,C_4)$
  2. 1) ROUND-2 OBJECTIVE
  3. 2) ROUND-1 FOUNDATION USED
  4. 3) NEW INSIGHT / TOOL (ROUND-2)
  5. 4) ATTACK PLAN (ROUND-2)
  6. 5) WORK (ROUND-2)
  7. 5.1 A linearized codegree lower bound
  8. Lemma 5.1 (linear $2$-path surplus bound).
  9. Proof.
  10. 5.2 Reiman-type bound recovered (sanity check)
  11. 5.3 Improved supersaturation for moderately large surplus $t$
  12. Proposition 5.2 (supersaturation for $t\ge 3n^{1.2625}$).
  13. Proof (following [HeMaYa19, Proposition 1.10]).
  14. Remark 5.3.
  15. 5.4 Updated small-$n$ information for $t=1$
  16. Theorem 5.4 (Qiao [Qiao20, Theorem 5]).
  17. 5.5 What still blocks the conjecture $h(n,1)=\Omega(\sqrt n)$
  18. 6) ADVERSARIAL VERIFICATION
  19. 7) FINAL
  20. 8) COMPLETION ESTIMATE (MANDATORY)
  21. 9) REFERENCES
  22. References

Erdős Problem #60 (Round 2): supersaturation just above $\mathrm{ex}(n,C_4)$

1) ROUND-2 OBJECTIVE

Path (A): attempt at a full proof, by closing the quantitative gap left in Round 1.

Round 1 produced a robust global lower bound on $\#C_4(G)$ from degree/codegree convexity, but it only forces many $4$-cycles when $e(G)$ exceeds $\tfrac12 n^{3/2}$ by a constant proportion. The conjecture asks for the far more delicate regime \[ e(G)=\mathrm{ex}(n,C_4)+1 \qquad\Rightarrow\qquad \#C_4(G)=\Omega(\sqrt n). \] In this round I introduce a sharper ("linearized") inequality relating $\#C_4(G)$ to the surplus of $2$-paths, and I push the unconditional supersaturation range substantially closer to the extremal threshold (though still not down to the $+1$ regime).

2) ROUND-1 FOUNDATION USED

I rely on the following Round-1 results exactly as stated there.
  • (R1--Lemma 1) Codegree formula: \[\#C_4(G)=\frac12\sum_{\{u,v\}} \binom{c(u,v)}{2},\] where $c(u,v)=|N(u)\cap N(v)|$ and the sum is over unordered vertex-pairs.
  • (R1--Lemma 2) Cauchy--Schwarz lower bound in terms of \[S:=\sum_{v}\binom{d(v)}{2}=\sum_{\{u,v\}}c(u,v)\qquad\text{and}\qquad N:=\binom{n}{2}:\] \[\#C_4(G)\ge \frac14\Big(\frac{S^2}{N}-S\Big).\]
  • (R1--Lemma 3) Jensen/convexity lower bound on $S$ from $m:=e(G)$: \[S\ge \frac{2m^2}{n}-m.\]
  • (R1--Corollary 4) Consequence: if $m\ge (\tfrac12+\varepsilon)n^{3/2}$ then $\#C_4(G)=\Omega_\varepsilon(n^2)$.
  • (R1--Computation) Exact small-$n$ values: $\mathrm{ex}(7,C_4)=9$ and every $7$-vertex graph with $10$ edges has at least one $C_4$; similarly $\mathrm{ex}(6,C_4)=6$ and there is a $7$-edge example with exactly one $C_4$.

3) NEW INSIGHT / TOOL (ROUND-2)

  1. A new lower bound that is linear (rather than quadratic) in the "$2$-path surplus": \[\#C_4(G)\ \ge\ \frac12\Big(M-\binom{n}{2}\Big),\] where $M:=\sum_v\binom{d(v)}{2}$ is the number of (unordered) length-$2$ paths. This bound appears (implicitly) in recent work and is the key to improved supersaturation when the edge surplus $t$ is subpolynomially small compared to $n^{3/2}$.
  2. New input from the literature beyond Round 1:
    • Qiao proved that for each $6\le n\le 11$ there exists a graph with $\mathrm{ex}(n,C_4)+1$ edges and exactly one $C_4$, while for $n\in\{12,13\}$ the minimum is $2$ copies [Qiao20, Theorem 5].
    • He--Ma--Yang proved the Erdős--Simonovits conjecture for the infinite family $n=q^2+q+1$ with even $q$, and also proved strong supersaturation for larger edge surpluses $t$ (in particular, $\#C_4(G)\ge \tfrac12 t\sqrt n$ for $t\ge 3n^{1.2625}$) [HeMaYa19, Proposition 1.10].

4) ATTACK PLAN (ROUND-2)

Round-1 gap. The Round-1 inequality $\#C_4\ge \tfrac14(S^2/N-S)$ is only useful when $S$ is at least a constant factor larger than $N$, which does not occur near the extremal threshold $m\approx \tfrac12 n^{3/2}$.

New plan.

  • Prove a sharper inequality $\#C_4\ge \tfrac12(M-\binom{n}{2})$ in terms of the number $M$ of $2$-paths.
  • Lower bound $M$ from $m$ by Jensen (Round-1 Lemma 3) and relate the relevant "surplus parameter" to $t=m-\mathrm{ex}(n,C_4)$ using known lower bounds on $\mathrm{ex}(n,C_4)$.
  • This yields an unconditional bound $\#C_4(G)\ge \Omega(t\sqrt n)$ for $t$ as small as $n^{1.2625}$ (a major strengthening over Round 1), while isolating the remaining obstruction for $t=1$.

5) WORK (ROUND-2)

5.1 A linearized codegree lower bound

Lemma 5.1 (linear $2$-path surplus bound).
Let $G$ be a simple graph on $n$ vertices. Let \[M:=\sum_{v\in V(G)}\binom{d(v)}{2}=\sum_{\{u,v\}} c(u,v) \qquad\text{and}\qquad N:=\binom{n}{2}. \] Then \begin{equation} \label{wsref-0-65-71-3a-6c-69-6e-65-61-72-5f-73-75-72-70-6c-75-73} \#C_4(G)\ \ge\ \frac12\,\max\Big\{0,\,M-N\Big\}. \end{equation}
Proof.
By (R1--Lemma 1), \[\#C_4(G)=\frac12\sum_{\{u,v\}} \binom{c(u,v)}{2}.\] For any integer $k\ge 0$ we have \[\binom{k}{2}=\frac{k(k-1)}{2}\ \ge\ \max\{0,k-1\}.\] Therefore \[ \sum_{\{u,v\}}\binom{c(u,v)}{2}\ \ge\ \sum_{\{u,v\}}\max\{0,c(u,v)-1\} =\sum_{\{u,v\}:\,c(u,v)\ge 1}(c(u,v)-1). \] Let $N_1:=|\{\{u,v\}:c(u,v)\ge 1\}|$. Then \[ \sum_{\{u,v\}:\,c(u,v)\ge 1}(c(u,v)-1)=\sum_{\{u,v\}}c(u,v)-N_1=M-N_1\ge M-N, \] because $N_1\le N$. Combining this with (R1--Lemma 1) yields \[\#C_4(G)\ge \frac12(M-N). \] If $M<N$ then the right-hand side is negative, so we may replace it by $\frac12\max\{0,M-N\}$ without weakening the inequality. $\square$

5.2 Reiman-type bound recovered (sanity check)

For a $C_4$-free graph, every pair of vertices has codegree $\le 1$ (else two common neighbors would form a $4$-cycle), hence $M=\sum_{\{u,v\}}c(u,v)\le N$. This is consistent with Lemma lem:linear_surplus.

Combining $M\le N$ with Jensen (R1--Lemma 3), i.e. \[M\ge \frac{2m^2}{n}-m,\] one gets the classical quadratic upper bound \begin{equation} \label{wsref-0-65-71-3a-72-65-69-6d-61-6e} \frac{2m^2}{n}-m\le \binom{n}{2} \qquad\Longrightarrow\qquad m\le \frac{n}{4}\left(1+\sqrt{4n-3}\right), \end{equation} which is a standard general upper bound on $\mathrm{ex}(n,C_4)$ (often attributed to Reiman).

5.3 Improved supersaturation for moderately large surplus $t$

Round 1 only forced many $C_4$ when $t=\Omega(n^{3/2})$. Lemma lem:linear_surplus enables a much smaller $t$ once we know a sufficiently good general lower bound on $\mathrm{ex}(n,C_4)$.
Proposition 5.2 (supersaturation for $t\ge 3n^{1.2625}$).
There exists $n_0$ such that for all $n\ge n_0$ and all real $t\ge 3n^{1.2625}$, \[ e(G)\ge \mathrm{ex}(n,C_4)+t\qquad\Longrightarrow\qquad \#C_4(G)\ge \frac{t\sqrt n}{2}. \]
Proof (following [HeMaYa19, Proposition 1.10]).
Let $m:=e(G)=\mathrm{ex}(n,C_4)+t$. Write \begin{equation} \label{wsref-0-65-71-3a-64-65-66-5f-73} m = \frac12\left(n^{3/2}+n\right)+s \qquad\text{for some real }s. \end{equation} He--Ma--Yang show that for all sufficiently large $n$ one has \begin{equation} \label{wsref-0-65-71-3a-65-78-5f-6c-6f-77-65-72} \mathrm{ex}(n,C_4)\ \ge\ \frac12\left(n^{3/2}-3n^{1.2625}+n\right) \qquad\text{(see \cite[Proposition~7.3]{HeMaYa19}).} \end{equation} Subtracting (eq:ex_lower) from (eq:def_s) yields \[s\ge t-\frac32 n^{1.2625} \ge \frac{t}{2}\qquad\text{since }t\ge 3n^{1.2625}. \] Next, Jensen gives a lower bound on the number $M$ of $2$-paths: \[ M=\sum_{v}\binom{d(v)}{2}\ \ge\ n\binom{\frac{2m}{n}}{2}. \] Using (eq:def_s), the average degree is \[\frac{2m}{n}=\frac{n^{3/2}+n+2s}{n}=\sqrt n+1+\frac{2s}{n}. \] A direct expansion gives \[ n\binom{\sqrt n+1+\frac{2s}{n}}{2} =\binom{n}{2}+2s\sqrt n+\frac{2s^2}{n}\; +\; \frac12\left(n^{3/2}+n\right)+s \ \ge\ \binom{n}{2}+2s\sqrt n+\frac{2s^2}{n}, \] so \begin{equation} \label{wsref-0-65-71-3a-4d-5f-6c-6f-77-65-72} M\ \ge\ \binom{n}{2}+2s\sqrt n+\frac{2s^2}{n}. \end{equation} Applying Lemma lem:linear_surplus gives \[ \#C_4(G)\ \ge\ \frac12\Big(M-\binom{n}{2}\Big)\ \ge\ s\sqrt n+\frac{s^2}{n}\ \ge\ \frac{t\sqrt n}{2}, \] using $s\ge t/2$ and $s^2/n\ge 0$. $\square$
Remark 5.3.
Proposition 5.2 strictly strengthens Round 1 by lowering the needed edge surplus from $\Theta(n^{3/2})$ to $\Theta(n^{1.2625})$. However, it is still far from the conjectured $t=1$ case.

5.4 Updated small-$n$ information for $t=1$

Define \[h(n,1):=\min\{\#C_4(G): |V(G)|=n,\ e(G)=\mathrm{ex}(n,C_4)+1\}.\] Round 1 verified $h(6,1)=h(7,1)=1$ and $h(5,1)=2$. Qiao proved the following extension.
Theorem 5.4 (Qiao [Qiao20, Theorem 5]).
For each $6\le n\le 11$ there exists an $n$-vertex graph with $\mathrm{ex}(n,C_4)+1$ edges and exactly one copy of $C_4$; for $n\in\{12,13\}$ every graph with $\mathrm{ex}(n,C_4)+1$ edges has at least two $C_4$'s.

Thus the exact values of $h(n,1)$ currently known for $5\le n\le 13$ are: \[ \begin{array}{c|ccccccccc} n & 5&6&7&8&9&10&11&12&13\\\hline h(n,1)&2&1&1&1&1&1&1&2&2 \end{array} \]

5.5 What still blocks the conjecture $h(n,1)=\Omega(\sqrt n)$

Lemma lem:linear_surplus shows that to prove $h(n,1)\ge c\sqrt n$ it would suffice to prove a lower bound of the form \[ M\ge \binom{n}{2}+\Omega(\sqrt n) \qquad\text{whenever }e(G)\ge \mathrm{ex}(n,C_4)+1. \] Equivalently, one needs to force an excess of $2$-paths over unordered pairs of order $\sqrt n$ at the $+1$ edge level.

Current unconditional approaches (including Round-1 convexity and the prime-gap based estimate (eq:ex_lower)) only force such an excess once the edge surplus $t$ dominates the uncertainty in the best known general lower bounds on $\mathrm{ex}(n,C_4)$, which is currently on the order $n^{1.2625}$ in [HeMaYa19].

A conceptually different input seems necessary for $t=1$:

  • either a global structural/stability theorem describing extremal and near-extremal $C_4$-free graphs for all $n$ (beyond the special family $n=q^2+q+1$),
  • or a new local counting principle showing that any one-edge extension of an extremal $C_4$-free configuration necessarily creates $\Omega(\sqrt n)$ many $C_4$'s.

6) ADVERSARIAL VERIFICATION

  • Lemma lem:linear_surplus edge cases. If $M\le N$, the bound gives $\#C_4\ge 0$, which is tautologically true. If $M>N$, the proof reduces to the inequality $\binom{k}{2}\ge k-1$ for $k\ge 1$ and the trivial bound $N_1\le N$; there are no hidden regularity assumptions.
  • Consistency with $C_4$-free graphs. If $G$ is $C_4$-free then all codegrees are $\le 1$, so $\sum \binom{c(u,v)}{2}=0$ and also $M\le N$. Hence Lemma lem:linear_surplus does not contradict extremality.
  • Proposition 5.2 dependence. The only nontrivial external input is the lower bound (eq:ex_lower) on $\mathrm{ex}(n,C_4)$ for general $n$, sourced to [HeMaYa19]. The remaining steps are algebra plus Jensen plus Lemma lem:linear_surplus.
  • Quantifier check. The conjecture concerns (eventually all) $n$ and $t=1$; Proposition 5.2 only applies for $t\ge 3n^{1.2625}$, so it does not settle the target statement.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 adds: (i) the sharper lower bound (eq:linear_surplus); (ii) a substantially improved unconditional supersaturation theorem for edge surplus $t\ge 3n^{1.2625}$ (yielding $\#C_4\ge \tfrac12 t\sqrt n$); and (iii) updated exact small-$n$ values of $h(n,1)$ through $n=13$ from [Qiao20]. The main conjecture $h(n,1)=\Omega(\sqrt n)$ remains open in general.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 55%

9) REFERENCES

References

  • [BloomErdos60] T. F. Bloom, Erdős Problem #60, Erdős problems website (problem page last edited 18 Nov 2025).
  • [HeMaYa19] Z. He, J. Ma, and T. Yang, Stability and supersaturation for the 4-cycle, arXiv:1912.00986.
  • [Qiao20] P. Qiao, On a problem of Erdős about graphs whose size is the Turán number plus one, arXiv:2001.11723.