Skip to content

Erdős Problem #1075

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: hypergraphs.

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

A hypergraph generalizes an ordinary graph: an edge can connect more than two vertices. An \(r\)‑uniform hypergraph has exactly \(r\) vertices in every edge.

Erdős Problem #1075 asks whether a hypergraph slightly denser than a balanced complete \(r\)‑partite construction must contain a growing subhypergraph whose edge density is uniformly larger than that construction's density.

More precisely, for every fixed \(r\ge3\), it asks for a constant \(c_r>r^{-r}\) such that every sufficiently large \(r\)‑uniform hypergraph with at least

\[ (1+\varepsilon)(n/r)^r \]

edges contains a subhypergraph with \(m=m(n)\to\infty\) vertices and at least \(c_rm^r\) edges. Critically, \(c_r\) must work for every \(\varepsilon>0\); it must not be quietly chosen separately for each \(\varepsilon\).

A small example

Divide \(n=rt\) vertices into \(r\) equally sized parts, each with \(t\) vertices. Make a hyperedge by choosing exactly one vertex from each part. The resulting complete \(r\)‑partite hypergraph has

\[ t^r=(n/r)^r \]

edges. If we similarly select \(m=rs\) vertices with \(s\) from each part, the selected hypergraph has \(s^r=r^{-r}m^r\) edges.

For \(r=3\), take three parts of two vertices each. There are \(n=6\) vertices and exactly \(2^3=8\) triples. This is the boundary example: it does not meet the problem's strict \((1+\varepsilon)\)‑times-boundary edge requirement. Adding a ninth triple can give a finite example above the threshold, but the conjecture is about larger and larger subhypergraphs as \(n\to\infty\).

What is known

The maintained catalogue records this question as open and locates its original formulation on page 80 of Erdős's 1974 paper Extremal problems on graphs and hypergraphs.

It also reports an earlier Erdős theorem from 1964 with the boundary value \(c_r=r^{-r}\) under a different positive-density hypothesis. Raising that value to a strict \(c_r>r^{-r}\) is the substantive new demand. A stronger hypothesis on the number of edges cannot simply be substituted without checking the exact dependence on \(\varepsilon\).

GCL's current state

Authenticated source audit #2346 fixes the quantifiers and independently proves the complete-partite edge-count identities. It confirms that the protected formal-conjectures snapshot has no available Lean statement for #1075.

The full 1964 and 1974 published proofs have not yet been examined page by page. The elementary construction explains the numerical boundary but is neither a proof nor a disproof of the desired uniform density increment.

What remains

The immediate obligation is to lock the original 1974 statement, distinguish induced and arbitrary subhypergraphs, and reconstruct the earlier 1964 density argument. The ensuing research challenge is to find a density-increment or amplification theorem uniform in \(\varepsilon\) and valid on a vertex set whose size diverges with \(n\).

Sources and claim boundaries

  • Erdős Problem #1075, original question and maintained open status.
  • P. Erdős, Extremal problems on graphs and hypergraphs (1974), p. 80, original source requiring full proof review.
  • P. Erdős, On extremal problems of graphs and generalized graphs (1964), Israel Journal of Mathematics, pp. 183–190.
  • Authenticated GCL audit #2346, independent elementary construction, not proof certification.

This manuscript remains an unaccepted editorial draft.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2346 — 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