OPEN
This is open, and cannot be resolved with a finite computation.
Let $r\geq 3$. There exists $c_r>r^{-r}$ such that, for any $\epsilon>0$, if $n$ is sufficiently large, the following holds.
Any $r$-uniform hypergraph on $n$ vertices with at least $(1+\epsilon)(n/r)^r$ many edges contains a subgraph on $m$ vertices with at least $c_rm^r$ edges, where $m=m(n)\to \infty$ as $n\to \infty$.
Erdős
[Er64f] proved that this is true with $c_r=r^{-r}$ whenever the graph has at least $\epsilon n^r$ many edges.
View the LaTeX source
This page was last edited 05 October 2025.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1075, https://www.erdosproblems.com/1075, accessed 2026-01-16
