Erdős Problem #1158
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 #1158. How dense can a uniform hypergraph be without containing the complete multipartite hypergraph whose edges choose one vertex from each class?
K_t(r) is complete t-partite t-uniform hypergraph with r vertices in EACH of t classes, containing r^t transversal t-edges. Let ex_t(n,K_t(r)) be largest t-edges of an n-vertex t-graph avoiding that configuration. Ask for ALL integers t,r≥2 whether ex_t(n,K_t(r))≥n^{t-r^{1-t}-o(1)} as n→∞. Interpret -o(1) as an exponent asymptotic and distinguish an unspecified multiplicative constant and the upper bound exponent.
A small example
For t=r=2, K_2(2)=K2,2=C4. Exhaustive 64 graph search on 4 labelled vertices finds ex_2(4,C4)=4. The proposed exponent is 2-2^{-1}=3/2. A single n=4 extremal count is not an asymptotic lower bound.
What is known
https://www.erdosproblems.com/1158 OPEN [Er64f],[Va99,3.65]. Erdős derived n^{t-O(r^{1-t})}≤ex_t(n,K_t(r)) ≪ n^{t-r^{1-t}}. The sharp lower exponent proposed is reported known only for graph case t=2 with r=2 or 3. For graph t=2,r=2 this is C4-free graph extremal n^{3/2}; related #714. No general t≥3 theorem claimed.
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 PARTIAL. Neither an original-paper proof review nor any Lean kernel replay or protected editorial acceptance has been completed.
What remains
ERDOS-1158-HYPERGRAPH-ZARANKIEWICZ-001: pin Erdős 1964 original proof and Kővári–Sós–Turán analogue for t-uniform case, verify constant uniformity in fixed t,r, examine finite incidence constructions and avoid conflating graph r=2/3 cases with full hypergraph conjecture.
Sharp general lower exponent OPEN; primary Erdős bound proof not independently reviewed.
Sources and claim boundaries
https://www.erdosproblems.com/1158 ; [Er64f],[Va99,3.65], #714; exact C4-free n4 count.
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: #2429 — 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.