上海创智学院李帅老师团队借助自研智能体系统与前沿AI模型,在经典超图二染色问题Property B的下界研究中取得一系列进展。此前,k=4的精确值m(4)=23已经确定;从k=5起,精确值仍未确定。团队针对k=5至12给出逐参数下界及候选结果,并以统一定理改进所有k>12的下界,研究范围覆盖全部尚未确定精确值的参数。适用于所有整数k≥12的下界优化定理,已完成端到端Lean形式证明,其给出的下界增量随每条超边的顶点数k呈指数增长。
一、一个文件分存问题背后的数学难题:不要把鸡蛋全放在一个篮子里
假设要把一批文件分存到两台服务器上,每个文件只存一份。我们希望每个项目涉及的文件都分布在两台服务器上,使任意一台服务器故障后,每个项目至少仍留下一个文件。如果项目之间没有共用文件,分配很容易;但同一份文件可能被多个项目共用,调整它的位置就会同时影响多个项目。当每个项目涉及的文件数固定时,至少需要多少个项目,才可能出现无论怎样分配都无法满足要求的情况?这一现实挑战正对应组合数学中的经典超图二染色问题Property B。
把每个文件看成一个顶点,把一个项目涉及的文件集合看成一条“超边”。普通图的一条边连接两个顶点,超图的一条边则可以包含多个顶点。如果每个项目都恰好涉及k个文件,就得到一个k元超图,也称k均匀超图。用红、蓝两色表示两台服务器,要求每条超边同时包含两种颜色,就意味着每个项目的文件都分布在两台服务器上。存在这样的染色方案,便称这个超图具有Property B。

图1 同一组文件的两种分存方式。项目甲涉及A、B、C,项目乙涉及B、C、D,共用文件B、C。左图中,每个项目的文件都分布在两台服务器上;右图中,项目甲的文件全部位于同一台服务器。右图这一分法不满足要求,而左图展示了一种可行的分法。每个项目恰好涉及三个文件,对应三元超图;红、蓝表示文件所在的服务器。
早在1961年,Erdős与Hajnal就系统研究了集合族具有Property B的条件[1]。1963年,Erdős进一步研究了一个极值问题:当每条边都包含k个顶点时,一个无法二染色的超图最少需要多少条边[2]?1964年,他进一步改进上界,继续缩小问题的上下界范围[3]。此后六十余年,研究者持续改进这一问题的上下界。如今,自动化科研正为这个经典问题的下界优化带来新的突破。
研究者用m(k)表示不具有Property B的有限简单k元超图的最少边数,其中“简单”指边集没有重复边。证明m(k)≥L,就意味着任意边数至多为L−1的有限简单k元超图都存在合法二染色。例如,m(6)≥67表示任意至多有66条边的六元超图都可以二染色,无论这些边如何重叠。
难点也正在这里:找到一个合法染色,只能解决一个具体实例;提高下界,则需要排除给定边数范围内的所有反例。同样数量的边,可以彼此独立,也可以以各种方式共享顶点;证明必须同时覆盖这些不同的结构。随着顶点数和边数增加,逐个枚举超图很快变得不可行。概率方法提供了另一条路径:设计一个随机染色过程,分析哪些事件会使它失败,只要能证明失败概率严格小于1,就能保证至少存在一个合法染色。因而,下界优化的关键之一,是在不遗漏任何超图的前提下,把失败概率估计得更准确。围绕超图二染色的下界研究,已有工作形成了以下代表性进展。
表1 Property B问题的代表性研究进展
年份 | 研究者 | 主要方法 | 主要进展 |
1961 | Erdős与Hajnal[1] | 集合族的二染色研究 | 系统研究Property B,提出最少边数问题并给出早期上界。 |
1963 | Erdős[2] | 概率方法 | 给出m(k)的早期下界与上界。 |
1964 | Erdős[3] | 概率方法 | 证明m(k)≤k²·2^(k+1),进一步改进上界。 |
1978 | Beck[4] | 概率方法 | 改进不可二染超图的最少边数下界。 |
2000 | Radhakrishnan与Srinivasan[5] | 重染方法:有选择地调整初始染色中部分顶点的颜色 | 证明存在常数c>0,使充分大的k满足m(k)≥c·2ᵏ√(k/ln k)。 |
2014 | Östergård[6] | 穷举计算 | 确定m(4)=23,解决四元情形的精确值问题。 |
2015 | Cherkashin与Kozik[7] | 随机贪心染色 | 为Radhakrishnan与Srinivasan的下界给出更简洁的证明。 |
2024 | Grill与Linzmayer[8] | 小参数分析 | 给出m(5)≥32、m(6)≥64、m(7)≥128、m(8)≥263、m(9)≥538。 |
二、为什么这一问题值得持续研究
Property B研究一种常见的约束冲突:每条限制单独都容易满足,放在一起却可能无法同时满足。提高m(k)的下界,就能在更大的约束范围内,保证无论这些限制如何重叠,都存在可行方案。这一问题与计算机科学中的约束满足问题直接相连。把每个顶点看成一个只能取“真”或“假”的变量,每条超边就对应一条要求:其中的变量不能全真,也不能全假。因此,超图二染色可以表述为一类布尔约束满足问题。超边共享顶点,对应不同约束共享变量;Property B下界给出的,正是这类约束必定能够同时满足的一种数量保证。这也解释了为什么下界的提高具有普遍意义:它提供的是对一整类约束系统的保证,适用于其中所有可能的共享方式,而非仅适用于某个经过挑选的结构。
在随机超图中,研究者还关心约束数量相对于变量数量增长到什么程度时,仍能以高概率保证可染。Achlioptas、Kim、Krivelevich与Tetali在2002年的研究给出了相应的可染性保证[9]。本次研究则要求结论覆盖给定边数范围内的所有超图。两类研究分别回答“通常会怎样”和“最不利情况下仍能保证什么”,共同帮助理解约束冲突的边界。Property B也将概率存在性证明与算法设计联系起来。更精细地分析随机染色为何失败,既提高可染性的保证范围,也为寻找合法染色提供算法思路。结构分析则帮助识别影响染色的关键依赖关系。例如,Erdős与Lovász在1975年的工作中,通过限制一条边与其他边的相交关系建立了可染条件,表明对局部依赖的控制可以带来整体可染性的保证[10]。
围绕这一问题,上海创智学院将自研智能体系统与前沿AI模型用于文献调研、路线设计、数学推导、精确计算与验证,沿两条相互联系的数学路线推进研究:一条针对具体参数,利用局部结构分析和精确计数提高整数下界;另一条面向一般参数,从超图内部的共同约束中提炼适用于所有k≥12的统一改进。研究者设定目标并判断结果,多智能体承担检索、推导、编程和审阅等具体任务;遇到反例或证明缺口时,研究返回相应步骤修订路线。文献、已证结论、失败路线及核验记录被持续记录,后续推导再读取这些材料,减少重复尝试,并使每项进展都能追溯到具体论证和证据。

图2 自动化科研推进超图二染色研究的方法总览。上方展示从问题与文献、路线迭代到证明推进、独立验证及成果交付的过程,研究知识库贯穿各环节;下方概括小参数精确计数与一般参数统一推导两条路线。
三、自动化科研推动开放参数的下界提升
目前,m(2)=3、m(3)=7、m(4)=23的精确值已经确定,其中四元情形由Östergård通过穷举计算解决[6];所有k≥5的精确值仍未确定[8]。在已有研究基础上,团队对k=5至12逐项推进下界,并将统一改进推广到所有k>12,覆盖全部尚未确定精确值的参数。表2汇总了已解的k=4情形与本次研究进展。
表2 Property B已解情形与本研究下界进展总表
顶点数k | 已有下界 | 本研究下界 | 增量 |
4 | 23(已闭合) | — | — |
5 | 32 | 35 | +3 |
6 | 64 | 67 | +3 |
7 | 128 | 131 | +3 |
8 | 263 | 267 | +4 |
9 | 538 | 543 | +5 |
10 | 1085 | 1112 | +27 |
11 | 2245 | 2275 | +30 |
12 | 4633 | 4664 | +31 |
>12 | BRS(k)+1 | BRS(k)+Δ(k)+1 | Δ(k)≥2随k指数增长 |
例如六元超图的下界从64提高到67,意味着能够保证可染的范围从至多63条边扩展到至多66条边。下界值每提高1,都需要证明多一条边时,所有这样的超图仍然可染。要得到这些新的下界,必须证明:在相应的边数限制下,无论顶点怎样安排、超边怎样重叠,超图都能二染色。因此,每个参数的推进都需要细致的数学分析,并结合计算与验证,确保没有遗漏可能的情形。
(一)先分析结构 再做精确计算
研究并不直接枚举所有超图,而是从假设存在的最小反例入手,利用顶点数、顶点度数以及每对顶点共同所属的边数等约束,缩小需要分析的范围。随后选取若干关键顶点,记录每条边与这些顶点的交集,将证明所需的信息整理为有限种局部配置,并逐类分析。关键在于,这些局部配置必须能够同时出现在同一个超图中。某处达到最不利状态时,可能已用掉其他位置达到最不利状态所需的边数或顶点度数,因此各处的最坏情况未必能够同时发生。研究利用这些配置之间共同满足的计数约束,收紧失败概率的上界,再对剩余必要情形进行精确计算。这样做的意义,在于把“所有超图”的庞大空间转化为由数学归约支撑的有限检查任务。计算只负责处理归约后仍需判断的情形,而哪些情形必须保留、哪些不可能同时出现,则由结构论证决定。
在这一过程中,AI智能体承担文献检索、候选推导、程序编写和证明整理等任务。不同模型对候选路线提出质疑,团队再根据反例、计算结果和数学论证修正推导。独立程序用于复核参数配置及概率计算,并结合覆盖检查确认必要情形没有遗漏。例如,八元和九元结果分别完成了全部2094种和3450种必要参数配置的独立精确复算,并通过额外的计数约束检查或决策树检查核对分类覆盖范围。
(二)让计算真正回到原问题
数值表中的每一项都通过检查,还不足以证明给定边数范围内的所有超图都可染。完整论证还必须说明每个需要处理的超图都落入已检查的分类,计算中的局部参数也需要与该超图相对应,并且计算结论最终能够推出原超图存在合法二染色。这种工作方式也让自动化探索中的失败可以继续发挥作用。探索中未能奏效的路线被保留下来,已发现的反例、已排除的方法和仍待解决的条件,都成为后续推导的依据。自动化探索因此形成持续迭代的过程:提出猜想,检验关键障碍,修正论证,再重新验证。例如,一条路线若只能处理某类局部配置,后续研究就必须补齐剩余情形;发现一个反例,也能帮助辨认先前忽略的共同约束。保留这些边界,使自动化探索积累的材料能够被后续证明继续使用,而不只是留下成功结果。
四、从小参数研究走向统一增益定理
小参数研究表明,利用同一个超图内部各结构之间的共同约束,可以进一步改善概率估计。在一般参数研究中,团队将这一思路用于“单交边对”,即恰好相交于一个顶点的两条边。这类边对是分析重染过程失败概率的重要对象[5]。如果将所有边对都按最坏情况计入,概率估计就可能过于保守。团队从最小反例的结构出发,构造一张辅助图:每个顶点代表原超图的一条边,两个顶点相邻表示对应的两条边恰好相交于一个顶点。团队证明,两两单交的边族大小受到限制,并据此给出单交边对总数更小的上界。将这一上界代回概率分析后,可染性的充分条件便能覆盖更大的边数范围。从逐参数计算走向统一定理,关键正是把有限情形中识别出的约束,转化为对整个参数范围都成立的结构限制。这样,改进就不再依赖逐一计算每个k,而是同时覆盖无限多个整数参数情形。
为了衡量这一改进,团队将已有概率分析中的估计整理成一个明确的可染色充分条件,并将满足这一条件的最大整数边数记为BRS(k)。已有结果保证,任意至多有BRS(k)条边的有限简单k元超图都可二染色,即m(k)≥BRS(k)+1;新定理证明,对所有整数k≥12,
m(k)≥BRS(k)+Δ(k)+1
其中,新增边数Δ(k)满足以下明确的下界:
Δ(k)≥⌊2(k/2)/[8(1+ln k)]⌋
指数项2(k/2)直接体现下界优化的指数增长。与已有概率分析中的基准相比,k=32时能够额外保证可染的边数至少增加2346条,k=64时至少增加152,837,269条,超过1.5亿条。这一定理适用于每条超边包含k个顶点、且k≥12的所有情形:在原有基准之上,能够保证二染色成功的边数进一步增加,而且新增边数随k呈指数增长。

图3 具体参数结果与统一增益保证。橙色点表示逐参数结果相对于选定参考下界的增量,紫色点表示加强判据在指定参数下直接求值所得的增量,两者读取左侧线性轴;蓝线表示统一公式保证的增益下限,读取右侧对数轴。
五、以多层验证支撑自动化探索
本研究结合模型审阅、独立程序复算和Lean形式证明开展验证。模型审阅用于发现潜在漏洞,程序复算用于核对分类覆盖与精确算术,Lean则逐步检查形式化证明中的逻辑推导。三者承担不同任务:模型审阅意见需要由具体论证支撑,程序核验也需要与分类完整性及原始命题相衔接。验证的重点除了是某个程序是否运行成功,还包括程序检查的范围是否完整、采用的假设是否已经证明,以及结果是否真正接回最初提出的数学问题。下界优化定理的Lean证明从任意有限顶点集和原始边集出发,证明基准预算的良定义与最大性,完成所需的结构归约和优化估计,最终得到使每条原边同时含有两种颜色的染色。
六、成果意义与后续方向
Property B下界的提高,意味着在不限制超边具体重叠方式的情况下,能够在更大的边数范围内保证存在合法二染色。此次研究既推动了具体参数的整数下界研究,也将局部配置之间的共同约束提炼为适用于所有整数k≥12的统一改进。这项工作展示了自动化科研在组合数学中的具体作用:从文献中提出可检验的研究路线,利用精确计算识别关键情形,再通过结构分析与严格验证形成完整论证。后续研究将继续完善候选结果的验证,探索更强的小参数下界,并研究这些共同约束能否进一步提升下界。自动化探索与可核查证明的结合,为持续推进这些问题提供了基础。
参考文献
[1] P. Erdős and A. Hajnal. On a property of families of sets. Acta Mathematica Academiae Scientiarum Hungaricae, 12:87–123, 1961.
[2] P. Erdős. On a combinatorial problem. Nordisk Matematisk Tidskrift, 11:5–10, 1963.
[3] P. Erdős. On a combinatorial problem. II. Acta Mathematica Academiae Scientiarum Hungaricae, 15:445–447, 1964. doi:10.1007/BF01897152.
[4] J. Beck. On 3-chromatic hypergraphs. Discrete Mathematics, 24(2):127–137, 1978. doi:10.1016/0012-365X(78)90191-7.
[5] J. Radhakrishnan and A. Srinivasan. Improved bounds and algorithms for hypergraph 2-coloring. Random Structures & Algorithms, 16(1):4–32, 2000.
[6] P. R. J. Östergård. On the minimum size of 4-uniform hypergraphs without property B. Discrete Applied Mathematics, 163(2):199–204, 2014. doi:10.1016/j.dam.2011.11.035.
[7] D. D. Cherkashin and J. Kozik. A note on random greedy coloring of uniform hypergraphs. Random Structures & Algorithms, 47(3):407–413, 2015. doi:10.1002/rsa.20556.
[8] K. Grill and D. Linzmayer. Improved lower bounds for Property B. arXiv preprint arXiv:2403.05674v3, 2024.
[9] D. Achlioptas, J. H. Kim, M. Krivelevich, and P. Tetali. Two-coloring random hypergraphs. Random Structures & Algorithms, 20(2):249–259, 2002. doi:10.1002/rsa.997.
[10] P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets, Vol. II, Colloquia Mathematica Societatis János Bolyai, 10:609–627. North-Holland, Amsterdam, 1975.
