Erdős Problem #714
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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 r≥2 let \(K_{r,r}\) denote the complete bipartite graph with r vertices in each part. Erdős asks whether \(\mathrm{ex}(n,K_{r,r})\) is bounded below by a constant times n^(2−1/r) for every fixed r (as n→∞), matching the classical Kövári–Sós–Turán upper exponent. The maintained page remains OPEN for general r, not for the known r=2 and r=3 instances.
A small example
\(K_{2,2}\) is exactly a four-cycle \(C_4\). A graph containing no \(C_4\) has any two vertices with at most one common neighbour. Hence \(\sum_v \binom{\deg(v)}{2}\le\binom{n}{2}\). Convexity then gives an \(O(n^{3/2})\) edge upper bound. For n=5 the five-cycle \(C_5\) has five edges and no 4-cycle, providing an exact but non-sharp small lower fixture.
What is known
Kövári–Sós–Turán 1954 proved \(\mathrm{ex}(n,K_{r,r})=O_r(n^{2-1/r})\). Known matching exponents hold for r=2, where \(\mathrm{ex}(n,C_4)=(1/2+o(1))n^{3/2}\), and for r=3 by Brown 1966 and independently Erdős–Rényi–Sós 1966. These constructions do not extend as an unconditional general r≥4 theorem. The source page was edited 2026-01-23; original KST54, Brown and ERS paper proofs were not independently read in this tranche.
GCL's current state
The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.
Preserved source-review qualifications: r general lower open; kst upper r2 r3 lower prior work. See the immutable 128-case critical review record for the complete source-return caveats.
What remains
ERDOS-714-C4-DOUBLE_COUNTING-TO-KST. Prove the exact C4-free common-neighbour count and Jensen upper bound, and create a small n=5 C5 witness. Then source-inspect the r=3 Brown/ERS finite-field construction and identify what breaks for r=4. Acceptance is a proved small-base-case inequality plus a source-locked higher-r missing lemma.
Sources and claim boundaries
Maintained Erdős #714; authenticated original issue #1985. Primary historical papers and complete formal dependencies not independently replayed. Critical source review, production merge, deployed math rendering and V2 admission remain outstanding.
Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1985 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
- 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.