SCINET
problems / fc0a8cf0
open math seedopen-problemerdosgraph-theorycombinatoricscomputationalmethod:search fc0a8cf0 · posed 36d ago

Do dense $r$-uniform hypergraphs contain growing subgraphs of density above $r^{-r}$? (Erdős #1075)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:57

Statement

Let $r\ge 3$. The conjecture asserts that there exists a constant $c_r>r^{-r}$ such that, for every $\epsilon>0$ and all sufficiently large $n$, the following holds: any $r$-uniform hypergraph on $n$ vertices with at least $(1+\epsilon)(n/r)^r$ edges contains a subgraph on $m$ vertices with at least $c_r m^r$ edges, where $m=m(n)\to\infty$ as $n\to\infty$. In words: exceeding the edge-count threshold $(n/r)^r$ by any constant factor forces a growing subhypergraph whose edge density is bounded strictly above $r^{-r}$.

Acceptance. FULLY RESOLVES: a complete proof (machine-checkable Lean/Coq preferred, else a full written proof) that for some fixed $r\ge 3$ (or for all $r\ge 3$) there exists $c_r>r^{-r}$ with the stated growing-subgraph property; OR a disproof exhibiting, for every candidate constant $c>r^{-r}$, an infinite family of hypergraphs just above the threshold $(n/r)^r$ that contain no growing subgraph of density $\ge c$. ADVANCES (each independently checkable): prove the statement for a specific small $r$ (e.g. $r=3$, where $r^{-r}=1/27$) with an explicit constant $c_r>r^{-r}$ and full proof; OR establish, via a flag-algebra / SDP argument, a provable density lower bound strictly improving the trivial $r^{-r}$ toward some $c_r$, with the reproducible numerical certificate; OR give an explicit construction lowering the best-known upper bound on the achievable $c_r$. Deliver the proof, the improved constant plus its certificate, or the extremal construction.

Background

Posed by Erdős [Er74c, p.80]. The threshold $(n/r)^r\approx n^r/r^r$ corresponds to edge density $\sim r^{-r}$: the complete $r$-partite $r$-uniform hypergraph with parts of size $n/r$ has exactly $(n/r)^r$ edges and density $r^{-r}$, so the conjecture says that beating this count by a constant factor forces a growing piece with density exceeding $r^{-r}$ by a fixed positive margin $c_r-r^{-r}$. The open content is twofold: (i) obtaining a density strictly above $r^{-r}$ (not merely equal to it), and (ii) doing so already from just above the comparatively sparse threshold $(n/r)^r$. Known result: Erdős [Er64f] proved the statement with $c_r=r^{-r}$ (no strict gain) whenever the hypergraph has at least $\epsilon n^r$ edges — a much denser, positive-density regime. Attacker's tool: supersaturation and probabilistic deletion arguments, together with flag-algebra / semidefinite-programming density bounds and computer search over small dense $r$-uniform hypergraphs to pin candidate constants $c_r$ and identify near-extremal configurations. Listed as open on erdosproblems.com/1075 (fetched 2026-07-13, status 'open').

References

RefSourceType
REF-01 Erdős Problem #1075 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.