跳到正文
arXiv math· Yangyan Gu, Rongxing Xu·· 7 天前精选AI 评分68

预印本构造反例表明强分数选择数可比选择数任意大

The strong fractional choice number can exceed the choice number by an arbitrarily large amount

AI 导读

一篇 arXiv 预印本证明,对任意整数 t≥0 与 b≥7t+2,存在选择数为 3 的平面图不是 (3b+t,b)-可选的,从而正面回答 Dvořák、Hu 和 Sereni 的问题,并否定 Li 和 Zhu 等提出的问题。

AI 深度导读基于原文整理的分节解读
背景
Erdős、Rubin 和 Taylor 曾问:对所有正整数 a、b、m,(a,b)-可选择性是否蕴含 (am,bm)-可选择性。Dvořák、Hu 和 Sereni 用 (a,b,m)=(4,1,2) 否定了这一猜测,并进一步追问:3-可选择的图是否可能不是 (6,2)-可选择的。此前的讨论中,Jiang 与 Zhu 之后,Li 与 Zhu 问是否每个 k-可选择图都是 (kb+1,b)-可选择的;等价地,Xu 与 Zhu 问是否对每个图 G 都有 ch_f^s(G) ≤ ch(G),其中 ch(G) 是选择数,ch_f^s(G) 是强分数选择数,定义为使 G 对所有满足 a/b ≥ r 的正整数 a、b 都 (a,b)-可选择的实数 r 的下确界。
做法
文中证明:对一切整数 t ≥ 0 与 b ≥ 7t+2,存在一个选择数为 3 的平面图,它不是 (3b+t,b)-可选择的。接着,对一切整数 k ≥ 4、t ≥ 0、b ≥ 3t+2,构造选择数为 k 的图,它不是 (kb+t,b)-可选择的,该构造的核心 gadget 只用六顶点轮 W_5;取 t=0、b=2 即回到 Dvořák、Hu 和 Sereni 的结果。最后,对每个充分大的整数 k,构造 ch(G)=k 的图 G,它不是 (2k+t,2)-可选择的,其中 t ≥ C√k,C > 0 是一个绝对常数。
结论
这些结果对 Dvořák、Hu 和 Sereni 的问题给出肯定回答,对上述另外两个问题给出否定回答,而且反例可以取在平面图上。在选择数为 3 的平面图上,ch_f^s(G) − ch(G) 的上确界至少为 1/7;对每个 k ≥ 4,选择数为 k 的图上该上确界至少为 1/3。多重度固定为 2 时差距仍然无界。文中进一步得到,当 k 趋于无穷时 k + Ω(√k) ≤ sup{ch_f^s(G) : ch(G)=k} ≤ 2^{(1+o(1))k}。
意义
标题所述结论由此成立:强分数选择数可以任意大地超过选择数。具体地,ch_f^s(G) ≤ ch(G) 这一命题一般不成立,Li–Zhu 与 Xu–Zhu提出的等价问题被否定回答,Dvořák、Hu 和 Sereni 关于 3-可选择图能否不是 (6,2)-可选择的问题被肯定回答。反例不仅存在于一般图,也存在于平面图这一限制较强的图类中;对 k ≥ 4,构造所用的核心 gadget 只是六顶点轮 W_5。
下一步
对 sup{ch_f^s(G) : ch(G)=k},正文给出的结果是下界 k + Ω(√k)、上界 2^{(1+o(1))k}(k 趋于无穷),两者之间仍有距离,正文未给出把这一区间收窄的结果。

本页是 AI 精读,不转载论文原文;完整论文(含方法、图表与参考文献)见原文

推荐理由

构造性反例把强分数选择数与选择数的差距推到无界,回答了多个悬置问题。

来源:arXiv math · arxiv.org