结果族 162：Counterexamples to Ryser’s covering conjecture · 学科：Combinatorics · 验证状态：暂无形式化证明，请以社区核验为准
想象一个社团组队：成员分成 q+1 个”部门”，每支小队恰好从每个部门各抽一人；社团有条铁律——任何两支小队必有共同成员。你是干事，想挑尽量少的人，使每支小队里至少有一人被挑中。Ryser 猜想说 q 个人就够；这篇论文证明：存在这样的社团，非 q+1 人不可——而且每个部门的人数还取到了理论上的最小值。
关键词卡片
看个具体例子
Ryser 猜想：@@M@@\tau\le(r-1)\nu@@；相交时 ν=1，即”q+1 个部门至多挑 q 人”。反例（数字版）：对每个足够大的素数 q，存在每部门恰 q+1 人的社团，@@M@@\tau=q+1@@——比预算恰好多一人。
构造从有限几何的”方向与直线”出发：每个方向设一个部门；把某方向的两条平行线合并、另两条拆成对角配对，使部门人数与覆盖难度同时抬升；再用概率方法选出兼容的拆分，最后借助”素平面稳定性”定理排除一切省人的覆盖方案。
为什么值得关心
Ryser 猜想是 König 定理向超图推广的核心关口，如今连”各部门等大”的平衡版本也被证伪。
暂无形式化证明（AI 结果待核验）
第一级台阶
入门导读的类比是社团组队：成员分属 q+1 个部门，每支小队恰好从各部门各抽一人，铁律是任何两支小队必有共同成员；干事想挑尽量少的人，使每支小队至少一人被挑中。半数学地说：对象是按部门分组的多方关系结构，基本元素是小队；操作是挑人去碰遍所有小队；Ryser 猜想说 q 个人总够用，本文证明存在非 q+1 人不可的社团。
第二级台阶
用本科术语精确化：顶点分成 r 组、每条边恰含每组一个元素的超图叫 r-部 r-一致超图；任何两条边都有公共点称为相交，此时两两不交的边至多一条，匹配数 @@M@@\nu=1@@；覆盖数 @@M@@\tau@@ 是碰到所有边的最少顶点数。Ryser 猜想断言 @@M@@\tau\le(r-1)\nu@@，r=2 时正是二部图情形的 König 定理。
第三级台阶
定理在这样的语境下陈述：对每个足够大的素数 q，存在相交的 (q+1)-部 (q+1)-一致超图，覆盖数为 q+1 且每部恰有 q+1 个非孤立顶点。素数假设挡住了末步所需的素平面稳定性定理对素域的要求；”足够大”挡住小 q 处概率估计的失效。结论用这些术语说：相交时预算是 @@M@@r-1=q@@，而构造达到上限 @@M@@\tau=r@@，连各部等大的平衡情形也推翻 Ryser 猜想，Gyárfás 单色树覆盖猜想的等价形式随之失效。
对每个足够大的素数 @@M@@q@@，本文构造出相交（intersecting）的 @@M@@(q+1)@@-部、@@M@@(q+1)@@-一致超图，覆盖数（covering number）达到理论上限 @@M@@q+1@@，且每部恰有 @@M@@q+1@@ 个非孤立顶点，从而推翻 Ryser 覆盖猜想——连”各部等大”的平衡情形也一并推翻。
Ryser 覆盖猜想断言：每个 @@M@@r@@-部 @@M@@r@@-一致超图（@@M@@r@@-partite @@M@@r@@-uniform hypergraph）@@M@@H@@ 满足 @@M@@\tau(H)\le(r-1)\nu(H)@@，其中 @@M@@\tau@@ 为覆盖数，@@M@@\nu@@ 为匹配数（matching number）。@@M@@r=2@@ 时即 König 定理，三部情形由 Aharoni 于 2001 年证明。相交超图中 @@M@@\nu=1@@，猜想退化为 @@M@@\tau\le r-1@@：Gyárfás 验证到秩 4，Tuza 到秩 5，线性相交情形到秩 9。截断射影平面在 @@M@@r-1@@ 为素数幂时给出 @@M@@\tau=r-1@@ 的取等例子，使这个界显得自然；Haxell–Scott 的一般下界却只有 @@M@@\tau\ge r-4@@。覆盖允许从各部混取顶点，要把覆盖数推过 @@M@@r-1@@ 极难，此前一直无人做到。
定理：存在阈值 @@M@@q_0@@，使对每个素数 @@M@@q\ge q_0@@，存在有限相交 @@M@@(q+1)@@-部 @@M@@(q+1)@@-一致超图 @@M@@H@@，满足 @@M@@|V_1|=\cdots=|V_{q+1}|=q+1@@、@@M@@\tau(H)=q+1@@，且每个顶点都属于某条边。因 @@M@@\nu(H)=1@@ 而 @@M@@r-1=q@@，这直接违反 Ryser 不等式。两端都是紧的：任一条边本身即覆盖，故 @@M@@\tau\le r@@；又任一部全体非孤立顶点构成覆盖，故 @@M@@\tau=r@@ 时每部至少需 @@M@@r@@ 个非孤立顶点，本构造在所有部同时取到该最小值。推论：对足够大的素数 @@M@@q@@，存在 @@M@@(q+1)@@-边染色完全图，其顶点需恰好 @@M@@q+1@@ 棵单色树（monochromatic tree）方能覆盖，Gyárfás 树覆盖猜想随之失效。
先从仿射平面对偶模型出发：在 @@M@@\mathbb{F}_q^2@@ 中，@@M@@q+1@@ 个方向各成一部，每部以该方向的 @@M@@q@@ 条直线为顶点，每个点对应一条由”过该点的各方向直线标签”组成的边。此图相交且 @@M@@\tau=q@@。为把覆盖数与各部大小同时抬到 @@M@@q+1@@，作者在每个方向改造直线划分：把两条平行线合并（merge）为一块，另取两条直线各保留四个指定点，按循环序 @@M@@u_0,u_1,u_2,u_3@@ 拆（split）成对角对 @@M@@\{u_0,u_2\}@@、@@M@@\{u_1,u_3\}@@ 两块，每部块数变为 @@M@@(q-4)+1+4=q+1@@。
第一个难点：拆分后同一直线上的两点可能失去该方向的公共标签，相交性濒临破裂。解法是把四个指定点安排成每个相邻对 @@M@@u_{i-1},u_i@@ 恰好同落进某个其他方向的合并块，而相邻对正是被对角拆分分开的点对，于是任意两个保留点仍共享某块，相交性得以保住。
第二个难点：排除混用多部标签、大小至多 @@M@@q@@ 的覆盖。论文先给出对任意有限域成立的确定性归约：若配置满足占用性（每条未删直线保留至少 @@M@@\rho q@@ 个点）、核覆盖集中性（覆盖核心 @@M@@R_0@@ 的 @@M@@\le q@@ 条线中至少 @@M@@(1-\rho/4)q@@ 条过同一射影点，即近似铅笔/pencil）及一个局部条件，则 @@M@@\tau=q+1@@。逻辑是：小覆盖先被逼成一支铅笔，占用性迫使铅笔内全部非拆分成员入选，剩余预算盖不住过中心的 @@M@@b@@ 条拆分直线上的 @@M@@4b@@ 个指定点，按中心在无穷远或在仿射点、以及 @@M@@b@@ 的大小分情形导出矛盾。
几何数据由概率方法产生：每方向独立抽取两条成分直线生成候选四元组，经不相容图与独立横截（independent transversal）选出兼容组合，并附带”预定 @@M@@s@@ 个槽”成功概率至多 @@M@@(K_*/q)^s@@ 的定量输出。删点定理在换测度（密度被 @@M@@e^{Kq}@@ 倍控制）下证明：@@M@@\le q@@ 条线的核心覆盖渐近必然盖住几乎全平面，形象计数（profile counting）给出 @@M@@\exp(-\Omega(q\log q))@@ 的节省，足以支付候选枚举与换测度代价。最后用 Szőnyi–Weiner 素平面稳定性定理把”几乎盖住全平面”化为”一支大铅笔”，这是需要 @@M@@q@@ 为素数的关键一步。各成功事件取交后概率为正，拼装出所需超图。
本文主结果暂无形式化证明，请以社区核验为准；定理中的阈值是渐近性的，未给出具体数值。姊妹篇在扩域阶 @@M@@q=s^n@@（@@M@@s\equiv2\pmod3@@、@@M@@n@@ 为大奇数）给出另一组反例，覆盖不同的秩范围，两篇构造相互独立，姊妹篇仅引用本文附录 A 的三条初等估计。按 OpenAI 官方声明，未经形式化的结果可能有问题，引用前宜待同行评议。
问 1：证明中最关键、也最脆弱的一步是哪里？
答：删点一节的换测度控制（deletion domination）：选定直线的条件分布被 @@M@@e^{K_0q}@@ 倍的一致律逐点控制，而在此扭曲测度下”任何至多 q 条线的核覆盖渐近必然盖住几乎全平面”，其关键计数把禁区形象类压到 @@M@@\exp(-\Omega(q\log q))@@。这笔节省必须同时付得起候选枚举与换测度的代价；若付不起，铅笔结构提不出来，确定性归约整体落空。
问 2：为什么 q 必须是素数，这个假设能去掉吗？
答：去不掉。”几乎盖住全平面”化为”一支大铅笔”用的是 Szőnyi–Weiner 的素平面稳定性定理，它只在素域阶成立。扩域阶的缺口由姊妹篇补上：@@M@@q=s^n@@（@@M@@s\equiv2\pmod3@@、n 为大奇数）给出另一组反例，但那篇不断言平衡。
问 3：与已有工作相比真正的新意是什么？
答：此前最好的一般下界是 Haxell–Scott 的 @@M@@\tau\ge r-4@@；Abu-Khazneh 等 2019 年的反例靠”加一个部”得到 (q+2)-部、覆盖数 q+1，恰好只取等而不违反不等式。本文首次在保持 @@M@@r=q+1@@ 部不变的同时把 @@M@@\tau@@ 推过预算到 r，且每部非孤立顶点数同时取到理论最小值，打破了”截断射影平面取等使界显得自然”的旧直觉。
问 4：这类 AI 参与生成的证明最可能在哪里出错？
答：条件化陷阱。三段概率估计——候选图界、独立横截的选择、删点控制——必须在同一实验上求交，而删点定理是在被选择过程扭曲后的测度下证的；若条件分布的逐点界在某角落失效，最后”减去三个失败概率仍为正”的装配论证就不成立。隐藏的条件独立错误是这类长概率论证的典型病灶，且本篇暂无形式化证明。
问 5：阈值 @@M@@q_0@@ 有多大？小素数处猜想如何？
答：论文明言阈值非数值化（”that threshold is not numerical”），只证存在性；小素数处猜想成立与否本文未展开，也未做计算搜索。两端紧性倒是干净的：任一条边即覆盖故 @@M@@\tau\le r@@，而 @@M@@\tau=r@@ 迫使每部至少 r 个非孤立顶点，构造同时取到。
问 6：谁会用到它？
答：超图覆盖与匹配理论社区，以及树覆盖方向：推论给出需要恰好 q+1 棵单色树的 (q+1)-边染色完全图，直接否定 Gyárfás 树覆盖猜想（Erdős–Gyárfás–Pyber 的等价性）；König 定理各种推广与拉丁方横截问题的研究者都会受波及。
总评
在 König 定理推广的主干道上落下的第一个平衡反例，@@M@@\tau@@ 与各部大小双双取到紧值，分量很重；最大风险在概率选择机制与素平面稳定性定理的衔接细节，无形式化背书，引用前宜待同行评议。