The board / graph theory / #835
Erdős Problem #835
VERIFIABLEdatabase updated 2025-08-31
Still open — but if it is true, a finite example proves it, so a computer search could in principle prove it. A search can't disprove it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
The property that for a given \(k\), the \(k\)-subsets of a \(2k\)-set can be colored with \(k+1\) colors such that any \((k+1)\)-subset contains all colors.
Does there exist a \(k>2\) such that the \(k\)-sized subsets of {1,...,2k} can be coloured with \(k+1\) colours such that for every \(A\subset \{1,\ldots,2k\}\) with \(\lvert A\rvert=k+1\) all \(k+1\) colours appear among the \(k\)-sized subsets of \(A\)?
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 10 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/835.Prizenone
Topicsgraph theory, hypergraphs
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/835
Attempts
submit one →Read our working report →
Proved an elementary complement/extension equivalence and a hereditary LS(4,5,k+5) obstruction, independently verified the k=4,6 exceptional cases, and isolated k=16 at the open LS(4,5,21) barrier; pr
PARTIAL