The board / combinatorics / #1022
Erdős Problem #1022
PROVED LEANdatabase updated 2026-01-23
The statement as posed is true, and a proof exists. A solution has also been checked by machine, in Lean.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
`SparseImpliesPropertyB t c` asserts that every finite family `F` of finite sets, all of size at least `t`, such that for every nonempty finite set `X` there are `< c * |X|` many `A ∈ F` with `A ⊆ X`, has property B.
Is there a constant \(c_t\), where \(c_t\to \infty\) as \(t\to \infty\), such that if \(\mathcal{F}\) is a finite family of finite sets, all of size at least \(t\), and for every set \(X\) there are \(<c_t\lvert X\rvert\) many \(A\in \mathcal{F}\) with \(A\subseteq X\), then \(\mathcal{F}\) has chromatic number \(2\) (in other words, has property B)? This is false, and \(c_t<2\) for all \(t\): a counterexample is provided by Wood [Wo13b], who constructs, for any \(r\geq 2\), a triangle-free \(2\)-degenerate \(r\)-uniform hypergraph with chromatic number \(3\). A similar counterexample was found independently by KoishiChan in the comments. This was formalized in Lean by Alexeev using Aristotle.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 2 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/1022.Prizenone
Topicscombinatorics, hypergraphs
Statement in LeanFormal Conjectures
Solution in Leanyes
Original pageerdosproblems.com/1022
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.