Skip to content

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?

\[ \mathrm{ex}_r(n,\mathcal F),\quad\mathcal F=\{H:|V(H)|=k,\ |E(H)|=s,\ H\ r\text{-uniform}\}. \]

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.

Back to catalogue · Compendium introduction