Wiki
Wiki

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 r≥2r\ge2 and d≥1d\ge1, an rr-uniform hypergraph that is triangle-free and dd-degenerate yet has chromatic number d+1d+1; a hypergraph is dd-degenerate when every subhypergraph has a vertex in at most dd edges, and a triangle is three edges whose union has r+1r+1 vertices. With r=tr=t and d=2d=2 this gives, for every t≥2t\ge2, a tt-uniform hypergraph without property B in which every nonempty vertex set XX contains at most 2(∣X∣−1)<2∣X∣2(|X|-1)<2|X| 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 ctc_t for which the implication of Problem 1022 holds must satisfy ct<2c_t<2, 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 χ≤d+1\chi\le d+1 for dd-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 22 (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 ctc_t-degeneracy, giving the family of all (n−1)(n-1)-subsets of an nn-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.