Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Claim. Theorem 3 of Wood's paper gives, for all integers and , an -uniform hypergraph that is triangle-free and -degenerate yet has chromatic number ; a hypergraph is -degenerate when every subhypergraph has a vertex in at most edges, and a triangle is three edges whose union has vertices. With and this gives, for every , a -uniform hypergraph without property B in which every nonempty vertex set contains at most edges: delete the vertices of the induced subhypergraph one at a time, each in at most two remaining edges, and charge every edge to its first deleted vertex. So a constant for which the implication of Problem 1022 holds must satisfy , and the answer to the problem is no. The paper does not mention the problem; it presents the theorem as showing that the greedy bound for -degenerate hypergraphs is sharp at every uniformity. The result page on the source card records the statement, the inductive construction of Lemma 4, and the application to the problem.
Claimant. David R. Wood, Hypergraph Colouring and Degeneracy, arXiv:1310.2972, posted 10 October 2013 (v1) and revised to v3 on 15 August 2014; the arXiv record lists no journal reference, so the paper is not recorded as refereed.
Acceptance. The site's curator, Thomas Bloom, names Wood's construction
[Wo13b] in the problem's commentary as the counterexample that refutes the
problem and bounds every valid constant below (reviewed). The paper was
pointed out in the problem's forum thread on 24 January 2026 by KoishiChan,
whose own construction had already been accepted
(claim page), with
the remark that the problem's counting condition is equivalent to degeneracy;
Bloom replied on 25 January 2026 that the condition is weaker than
-degeneracy, giving the family of all -subsets of an -set as
an example, and that degeneracy implies the condition, which is all the
disproof needs. No Lean development declares itself a formalization of Wood's
construction.