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

Updated Oct 8

Problem 834

claims/: The 1 claim page of Problem 834, one per claimant's result; the problem's standing derives from them.

Statement. Does there exist a $3$ -critical $3$ -uniform hypergraph in which every vertex has degree $\geq 7$ ?

Formulation. Erdős and Lovász do not say what $3$ -critical means, as the site's commentary notes, and the commentary records two readings, which this page follows: transversal criticality ( $\tau(H)=3$ and $\tau(H-e)\le2$ for every edge $e$ ) and chromatic criticality (weak chromatic number $3$ , with $H-e$ and $H-v$ $2$ -colorable for every edge $e$ and vertex $v$ ). The standing judges the site's wording, the Statement above; Li answers it no under the first reading and yes under the second, so the claim value is answered.

Status. Solved.

Source. P. Erdős, Unsolved Problems (1974), pp. 278--297, problem on p. 282, MR360350 [Er74d], as identified by erdosproblems.com/834, accessed 2026-09-05. Page 282 of [Er74d] is not held; the wording and attribution of the problem rest on the site. Website citation: T. F. Bloom, Erdős Problem #834, https://www.erdosproblems.com/834, accessed 2026-09-05.

References.

[Er74d] P. Erdős, Unsolved Problems. (1974), 278--297. MR360350.
[Li25] R. Li, On an Erdős-Lovász problem: $3$ -critical $3$ -graphs of minimum degree $7$ . arXiv:2512.24850 (2025).

Formalization. Statement in formal-conjectures, added on 2026-10-07. The file states the transversal reading as erdos_834.parts.i, with the answer no, and the chromatic reading as erdos_834.parts.ii, with the answer yes; both are tagged research solved with sorry bodies and no formal_proof pointer. A statement file is not a formalization of a result, and no Lean proof of either reading is known.

Current assessment

Li [Li25] treats both readings of " $3$ -critical" that the Formulation records.

The site marks the problem solved because [Li25] settles both documented readings. The site's discussion also argues from historical context and later terminology that the chromatic reading is likely the intended one. A comment in the discussion thread (4 December 2025), however, identifies [Er74d] with the title of the 1975 Erdős--Lovász paper, in conflict with the [Er74d] entry under References, Erdős's 1974 Unsolved Problems. The comment is therefore contextual evidence rather than verification of [Er74d, p. 282], which is not held.

The accepted claim page Li 2025 states both results, the reason the claim value is answered rather than proved or disproved, and the acceptance evidence: the site's curator marks the problem solved and credits Li under both readings, while the paper is an arXiv preprint with no journal record. The corpus's own review of Li's thirteen reconstructed proofs, recorded on the source card's evidence pages, is the project's review and gives no acceptance evidence.

Search scope, 2026-10-07: the site's problem page and discussion thread, the community database (teorth/erdosproblems) and the formal-conjectures statement file. No claim other than Li's was found.

Progress

Under the transversal interpretation, a 3-uniform hypergraph $H$ is critical of order three when

\tau(H)=3\quad\text{and}\quad \tau(H-e)\leq2 \quad(e\in E(H)).

Li proves that every such $H$ has at most ten edges. Since $\tau(H)=3$ forces at least five vertices, the degree-sum identity then gives $\delta(H)\leq6$ . Thus the answer to the stated degree-seven question is no under this meaning, and the bound is sharp for $K_5^{(3)}$ .

Under the chromatic interpretation, criticality means weak chromatic number three together with

\chi(H-e)\leq2\quad(e\in E(H)),\qquad \chi(H-v)\leq2\quad(v\in V(H)).

Li gives a 22-edge example on nine vertices. Its degree sequence is $(10,7,7,7,7,7,7,7,7)$ ; it is not 2-colorable, has an explicit proper 3-coloring, and has explicit 2-coloring certificates after every edge or vertex deletion. Hence the answer is yes under this meaning.

Known Results

Li's Theorem 1.1: transversal-critical 3-graphs of order three have minimum degree at most six, sharply.
The ten-edge theorem: the key set-pairs argument behind the transversal bound.
Li's Theorem 1.2: a critically 3-chromatic 3-graph of minimum degree seven exists.
The nine-vertex construction: the complete edge list, with links to the degree, coloring, and deletion proofs.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (20)

Li's resolution of both readings of 3-critical problems/set_systems/E0834/claims Set Systems, Designs and Hypergraphs set_systems/li_2025_erdos_lovasz_problem_3_critical Corollary 3.4: the transversal-critical degree bound Review of Li's two critical-hypergraph proofs Lemma 2.2: an edge-deletion colouring criterion Lemma 3.1: Bollobás's set-pairs inequality Lemma 4.2: degree sequence of the construction Lemma 4.3: the construction is not 2-colourable Lemma 4.4: a proper 3-colouring of the construction Proposition 3.5: sharpness of the transversal degree bound Proposition 4.5: edge-criticality of the construction Proposition 4.6: vertex-criticality of the construction Theorem 1.1: sharp negative answer under transversal criticality Theorem 1.2: positive answer under chromatic criticality Theorem 3.2: at most ten edges under transversal criticality Theorem 4.1: the nine-vertex construction Tuza: Critical hypergraphs and intersecting set-pair systems Theorem 17 (p. 142): an r-uniform tau-critical hypergraph with tau = t has at most n_1(r, t-1) < binomial(t+r, r) vertices

Graph