Erdős Problem #766
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 k-vertex graphs F with exactly l edges, define f(n;k,l)=min_F ex(n,F), where ex(n,F) is the greatest edge count of an n-vertex graph with no copy of F. Erdős asks for estimates when k<l≤k²/4 and whether, for fixed k and large n, f is STRICTLY increasing as l increases. This is OPEN. An elementary monotonic nondecreasing inequality DOES hold and must not be misreported as strict monotonicity.
A small example
If H has l+1 edges on a fixed k-vertex set, delete any one edge to form F with l edges. Every F-free graph is H-free; hence ex(n,F)≤ex(n,H). Minimizing over all H gives f(n;k,l)≤f(n;k,l+1), for feasible l. The inequality need not be strict from this argument. For k=6 the target range is 6<l≤9, so compare l=7,8,9 rather than choosing an empty range such as k=4.
What is known
Dirac and Erdős separately proved that just outside the target upper range, l=floor(k²/4)+1, one has f(n;k,l)≤floor(n²/4)+1. This boundary result does not answer the strict increase across every adjacent integer l IN the interval. The maintained #766 OPEN status and graph conventions are source-based; the complete Erdős 1964 statement and extremal proof not independently read.
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: general f n k l open; monotone nondecreasing not eventual strict. See the immutable 128-case critical review record for the complete source-return caveats.
What remains
Formally prove monotone nondecreasing f via one-edge deletion, then enumerate k=6 graphs with l=7,8,9 up to graph isomorphism for small n to seek equal consecutive values. Specify 'strict' as f(n;k,l+1)>f(n;k,l) for all sufficiently large n and fixed k; finite cases only falsify at a fixed n, not asymptotic eventual strictness.
Sources and claim boundaries
Maintained #766, authenticated original issue return. Complete original proof pages pending; no new independent primary theorem certification production merge, deployed browser mathematics QA or editorial admission.
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: #2037 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_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.