Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. Problem 834 asks whether a 33-critical 33-uniform hypergraph can have every vertex of degree at least 77, and its source does not say what 33-critical means. Li's paper settles the question under both meanings documented in the site's commentary, with opposite answers.

Under the transversal meaning, HH is 33-critical when some set of three vertices meets every edge, no set of two vertices does, and for every edge ee some pair of vertices meets every edge other than ee (τ(H)=3\tau(H)=3 and τ(H−e)≤2\tau(H-e)\le2 for every edge ee). Theorem 1.1 of the paper proves that such a 33-uniform hypergraph has a vertex of degree at most 66, so the answer is no; the bound is sharp, attained by the complete 33-uniform hypergraph on five vertices. The argument (Theorem 3.2) pairs each edge with a two-vertex transversal of the rest and applies Bollobás's set-pairs inequality, which bounds the number of edges by (52)=10\binom{5}{2}=10; with at least five vertices the degree sum then forces a vertex of degree at most 66.

Under the chromatic meaning, HH is 33-critical when its weak chromatic number is 33 and deleting any edge or any vertex leaves a 22-colorable hypergraph. Theorem 1.2 exhibits a 33-uniform hypergraph on nine vertices with 2222 edges and degree sequence (10,7,7,7,7,7,7,7,7)(10,7,7,7,7,7,7,7,7) that is not 22-colorable, has a proper 33-coloring, and has an explicit proper 22-coloring after each of the 2222 edge deletions and nine vertex deletions (Theorem 4.1 and Propositions 4.5 and 4.6), so the answer is yes.

The claim value is answered because the result is neither a proof nor a disproof of one statement: the two readings of the question receive opposite answers, and the paper settles both. The source card holds the digest and one page per result.

Claimant. Ruiliang Li, On an Erdős–Lovász problem: 3-critical 3-graphs of minimum degree 7, arXiv:2512.24850, posted 31 December 2025 (v1, 16 pages). The arXiv record lists no later version and no journal reference, so the paper is not recorded as refereed.

Acceptance. The site's curator, Thomas Bloom, marks Problem 834 as solved and credits Li [Li25] with both outcomes, the degree bound under the transversal reading and the nine-vertex example under the chromatic reading (reviewed); the paper was reported in the problem's forum thread on 1 January 2026, and the site's page was updated on that date. The corpus's own reading of the thirteen result pages and its finite checks of the construction, recorded on the source card's evidence pages, are the project's review and give no acceptance evidence. No Lean formalization of either result is known; the formal-conjectures statement file, linked from the problem page, states both readings as research solved with sorry bodies and no formal_proof pointer, and a statement file is not a formalization.