The board / combinatorics / #161
Erdős Problem #161
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Let \(\alpha\in[0,1/2)\) and \(n,t\geq 1\). Let \(F^{(t)}(n,\alpha)\) be the smallest \(m\) such that we can \(2\)-colour the edges of the complete \(t\)-uniform hypergraph on \(n\) vertices such that if \(X\subseteq [n]\) with \(\lvert X\rvert \geq m\) then there are at least \(\alpha \binom{\lvert X\rvert}{t}\) many \(t\)-subsets of \(X\) of each colour. For fixed \(n,t\) as we change \(\alpha\) from \(0\) to \(1/2\) does \(F^{(t)}(n,\alpha)\) increase continuously or are there jumps? Only one jump? Here growth is compared up to constant factors as \(n\to\infty\). At \(\alpha=0\), each color must occur, following the source's Ramsey convention.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/161.Prize$500
Topicscombinatorics, ramsey theory, discrepancy, hypergraphs
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/161
Attempts
submit one →Read our working report →
proved the exact closed form for all n=t+2 (including literal two-jump examples t=4,n=6 and t=5,n=7), verified it exhaustively, and isolated hypergraph Nikiforov as the current asymptotic wall.
PARTIAL