Skip to content

Erdős Problem #765

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (not automatically the live result).
Subject areas: graph theory, turan number.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

For a finite simple graph, \(\mathrm{ex}(n,C_4)\) is the maximum number of edges among graphs on \(n\) vertices that contain no four-cycle. The following leading asymptotic is PROVED using projective-plane constructions and Reiman's upper bound:

\[ \mathrm{ex}(n,C_4)\sim\tfrac12 n^{3/2}. \]

However Erdős's STRONGER proposed second-order formula

\[ \mathrm{ex}(n,C_4)=\tfrac12 n^{3/2}+\tfrac14 n+O(\sqrt n) \]

is DISPROVED by Ma and Yang (2023). The maintained 'SOLVED (LEAN)' aggregate must not suggest both statements have affirmative proofs.

A small example

The five-cycle \(C_5\) has five vertices, five edges, and contains no four-cycle; hence \(\mathrm{ex}(5,C_4)\ge5\). In ANY graph containing no \(C_4\), two different vertices have at most one common neighbour, because two common neighbours would create a 4-cycle. Counting two-edge paths gives the bound

\[ \sum_v\binom{\deg(v)}{2}\le\binom{n}{2}. \]

This is the elementary basis for the \(O(n^{3/2})\) upper bound.

What is known

Brown and independently Erdős–Rényi supplied finite projective-plane/polarity graph constructions with \(n=q^2+q+1\) and at least \(\tfrac12 q(q+1)^2\) edges, leading with Reiman's upper bound to

\[ \lim_{n\to\infty}\frac{\mathrm{ex}(n,C_4)}{n^{3/2}}=\tfrac12. \]

Füredi proved exact counts for these \(n\) when \(q>13\). Ma and Yang's 2023 peer-reviewed publisher abstract explicitly confirms that their new extremal upper bound disproves Erdős's second-order conjecture with linear coefficient 1/4. The maintained catalogue further reports a positive-density quantitative strengthening; that exact stronger formulation is attributed to the catalogue pending full-paper replay. The site's 2026 external LEAN status does not constitute GCL kernel replay; full modern theorem and formal proof pages not inspected.

GCL's current state

The authenticated original source report records STATUS_CONFLICT and source status; for #765 it deliberately separates proved leading asymptotic from a false second-order conjecture. This is an editorially reviewed explanatory article under protected batch EC-BULK-005-R3. Its original STATUS_CONFLICT source record remains preserved; editorial admission does not certify a new mathematical theorem or a GCL formal proof.

What remains

Keep the leading-term PROVED and second-order DISPROVED outcomes separate; verify the stronger positive-density quantifier in the complete Ma–Yang proof before internally certifying it. Prove common-neighbor double counting and exact C5 fixture; recover any external formal proof hash/axiom closure only if independently verified.

Sources and claim boundaries

Maintained #765, Ma–Yang 2023 publisher abstract, authenticated original issue return. Complete original proof pages pending; protected publication and live browser mathematical rendering are completed; exact-hash V2 admission and proof-level verification are separate.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2036 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction