Erdős Problem #1157
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: hypergraphs, 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.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
Erdős Problem #1157. How many hyperedges can a uniform hypergraph have when no small group of vertices supports a prescribed number of edges?
For r-uniform hypergraphs, let F be the family of ALL r-graphs with k vertices and s edges, and ex_r(n,F) the largest number of edges in an n-vertex r-graph containing no member of F. This is equivalently forbidding s distinct edges supported on at most k vertices, subject to exact definitions and isolated vertices. Maintained question's introduction says 'Let t,k,r≥2' but uses s without binding it and does NOT use t in ex_r; flag source TYPO/variable mismatch, require 1≤s≤binom(k,r), k≥r. Don't confuse the cited Brown–Erdős–Sós t-uniform general conjecture with this r-uniform extremal quantity.
A small example
For r=2,k=3,s=3 forbidden family is K3; Mantel's theorem ex_2(5,K3)=6, verified by exhaustive enumeration of 1024 labelled graphs. For r=3,k=4,s=2, any two 3-edges on 4 vertices violate, giving ex_3(4,F)=1. These exactly computed cases do not settle general asymptotics.
What is known
https://www.erdosproblems.com/1157 OPEN, Brown–Erdős–Sós [BES73], Vardi [Va99,3.64]. For k>r,s>1 a general lower bound ex_r(n,F)≫_{k,s} n^{(rs-k)/(s-1)} is reported. Their broader conjecture ex_t(n,F)=o(n^t) for r>t≥2,s≥3,k≥(r-t)s+t+1 concerns separately parameterized t-uniform graphs and is linked #1178. Special 3-uniform (k,s) cases #716,#1076. Bound's significance depends on exponent and parameter conditions.
GCL's current state
Authenticated original-issue source return establishes the bounded question, relevant external results, and independently tested finite fixture. The reproducible checks are in ci/erdos_compendium_007_phase18_checks.py.
The source return disposition is STATUS_CONFLICT. Neither an original-paper proof review nor any Lean kernel replay or protected editorial acceptance has been completed.
What remains
ERDOS-1157-BES-SOURCE-PARAMETERS-001: read BES73 original, repair unused t/unbound s in catalogue statement with exact original source, distinguish induced versus non-induced and isolated vertices. Verify lower-bound exponent, its domain and the t-uniform broader conjecture separately.
Source statement variable-binder mismatch; source-fidelity review pending; general problem OPEN.
Sources and claim boundaries
https://www.erdosproblems.com/1157 ; [BES73],[Va99,3.64], #1178,#716,#1076; exact finite extremal examples.
This is a locally validated, UNACCEPTED editorial draft. Assertions beyond the exact finite checks are attributed to original external sources and remain subject to source-fidelity review.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2428 — 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.