Erdős and Lov'asz asked whether there exists a "3-critical" 3-uniform hypergraph in which every vertex has degree at least 7. The original formulation does not specify what 3-critical means, and two non-equivalent notions have appeared in the literature and in later discussions of the problem. In this paper we resolve the question under both interpretations. For the transversal interpretation (criticality with respect to the transversal number), we prove that a 3-uniform hypergraph $H$ with $τ(H)=3$ and $τ(H-e)=2$ for every edge $e$ has at most 10 edges; in particular, $δ(H)\le 6$, and this bound is sharp, witnessed by the complete 3-graph $K^{(3)}_5$. For the chromatic interpretation (criticality with respect to weak vertex-colourings), we give an explicit 3-uniform hypergraph on 9 vertices with $χ(H)=3$ and minimum degree $δ(H)=7$ such that deleting any single edge or any single vertex makes it 2-colourable. The criticality of the example is certified by explicit witness 2-colourings listed in the appendices, together with a short verification script.
翻译:Erdős和Lovász曾提出是否存在一个"3临界"的3一致超图,其中每个顶点的度至少为7。原始表述并未明确"3临界"的含义,文献及后续讨论中出现了两种不等价的定义。本文在两种解释下均解决了该问题。对于横截数解释(关于横截数的临界性),我们证明了满足$τ(H)=3$且对每条边$e$有$τ(H-e)=2$的3一致超图$H$至多有10条边;特别地,$δ(H)\le 6$,且该界是紧的,由完全3图$K^{(3)}_5$所证实。对于着色解释(关于弱顶点着色的临界性),我们显式构造了一个9顶点、满足$χ(H)=3$且最小度$δ(H)=7$的3一致超图,使得删除任意单条边或单个顶点后其可2着色。该例子的临界性由附录中列出的显式见证2着色及简短验证脚本所证实。