Status
On this page
Status
Topics
Status
On this page
Status
Topics
Is there a constant , where as , such that if is a finite family of finite sets, all of size at least , and for every set there are many with , then has chromatic number (in other words, has property B)?
Is there a constant , where as , such that if is a finite family of finite sets, all of size at least , and for every nonempty set there are many with , then has chromatic number (in other words, has property B)?
Source: erdosproblems.com/1022
An accepted solution exists. The statement is false.
PROVED (LEAN) on erdosproblems.com (page last edited 25 January 2026); the site's own commentary says the statement is false, names Wood's construction [Wo13b] as the counterexample with for every , and credits KoishiChan with an independent counterexample in the comments; the label's Lean mark refers to the Lean proof listed under Formalization, which proves the negation of the corrected Statement. The page therefore departs from the site's label: the corrected Statement is disproved.
The site's wording quantifies over every set , the empty set
included; at its hypothesis reads , which never holds, so
no family meets it and the question as printed is answered yes for every choice
of , for want of an instance. The defect is Erdős's: [Er71] Problem 17
(p. 105) takes the count "for every ", and the site's curator,
Thomas Bloom, quoted that sentence in the problem's thread on 4 December 2025
and called the site's statement an accurate rephrasing of it. Bloom reads the
question with nonempty. The site's commentary (page last edited 25 January
2026) calls the statement false and names Wood's construction [Wo13b] and
KoishiChan's as counterexamples, which refute it only once is nonempty; the
Lean statement that Boris Alexeev posted in the thread on 22 January 2026, whose
hypothesis is X.Nonempty, is the one Terence Tao recorded as the formalization
of KoishiChan's solution and the one the label's (LEAN) mark refers to; and on
23 January 2026 Bloom wrote of marking the problem solved by KoishiChan "since
this answers the question as I understand it". The corrected Statement inserts
"nonempty" before "set " and changes nothing else; the formal-conjectures
statement requires nonempty as well. Under the printed wording the answer
is yes, vacuously; under Bloom's reading it is no: Wood's theorem gives
and KoishiChan's construction for every , and Lovász's
theorem with [KN99] gives the exact value (Known Results). No result about
the printed wording exists beyond the vacuity check recorded here. The site's
label PROVED (LEAN) has the polarity of a positive answer; it contradicts the
site's own commentary and the Lean proof of the negation, and the page follows
the commentary (Status).