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着色及简短验证脚本所证实。

0
下载
关闭预览

相关内容

何恺明&Lecun新论文CVPR2025《无需归一化的 Transformer》
专知会员服务
18+阅读 · 2025年3月15日
NeurIPS 2021 | 寻找用于变分布泛化的隐式因果因子
专知会员服务
17+阅读 · 2021年12月7日
专知会员服务
50+阅读 · 2021年6月2日
专知会员服务
42+阅读 · 2021年4月2日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
40+阅读 · 2020年8月22日
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
VIP会员
相关VIP内容
何恺明&Lecun新论文CVPR2025《无需归一化的 Transformer》
专知会员服务
18+阅读 · 2025年3月15日
NeurIPS 2021 | 寻找用于变分布泛化的隐式因果因子
专知会员服务
17+阅读 · 2021年12月7日
专知会员服务
50+阅读 · 2021年6月2日
专知会员服务
42+阅读 · 2021年4月2日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
40+阅读 · 2020年8月22日
相关资讯
图节点嵌入(Node Embeddings)概述,9页pdf
专知
15+阅读 · 2020年8月22日
【NeurIPS2019】图变换网络:Graph Transformer Network
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
条件概率和贝叶斯公式 - 图解概率 03
遇见数学
10+阅读 · 2018年6月5日
相关基金
国家自然科学基金
0+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员