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:
However Erdős's STRONGER proposed second-order formula
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
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
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.