单交结构带来的统一整数增益
本文证明:对每个整数 ,由指定 RS 重染判据得到的整数可染预算可以统一增加一个显式的正整数。所有染色结论均适用于任意有限简单 元超图。
定理、引理与完整证明 · 文献引用按所列版本标注
三类结果:逐项下界、加强判据求值与统一公式
是不可二染的有限简单 元超图所需的最少边数。从已知精确值 出发,本项目与合作者的工作在同一参考包络下展示三类结果: 的逐项具体下界、本文结构加强判据C.2在 的精确求值,以及对每个整数 成立的统一增益定理。逐项结果利用各参数的结构与精确计算证书。紫色与蓝色来自我们的同一个加强判据:紫色直接选取参数并严格求值,得到指定 的更强数值;蓝色通过统一估计,导出适用于所有 的简洁公式。 该判据在正文编号为推论C.2。
逐项具体下界 · k = 5–1235 · 67 · 131 · 267 · 543 · 1112 · 2275 · 4664本项目与合作者的纸面证明/局部精确证书
我们的加强判据 · k = 12、13m(12) ≥ 4647 · m(13) ≥ 9564直接求值:增益14、25;严格数值证书
我们的统一公式 · 全部 k ≥ 12旧组合基线 + 增长的整数增益同一统一定理已对全部 k≥12完成端到端Lean
左右滑动图像,可查看完整坐标与图例。
经典超图二染色问题 Property B |小参数到一般定理,下界系统提升
差值主图。 红色逐项结果、紫色加强判据点与蓝色统一公式使用同一定义的参考包络 :取正文已核五项明确参考式,并在 加入 GL Theorem 1 的具体下界后取最大值。这是指定参考集的共同包络,不称全部文献的世界最佳。全图共用同一条线性的 横轴;红色读左侧线性轴,表示逐项结果的增益 。 依次增加3、3、3、4、5、27、30、31; 的零增量只标记既有精确值23。蓝色读右侧对数轴,表示统一定理相对同一包络保证增加的整数下限 。对每个 ,共同包络恰为 。
紫色图例“Our refined criterion: certified evaluation”表示我们的加强判据直接求值;蓝色“Our uniform formula (Lean)”表示由同一判据推导的统一公式。 紫色菱形也读左侧线性轴,给出: 为 , 为 。这些是基于一般充分性证明、经独立数值复算的具体下界,不是新的文献基线,也不称这两项数值已经Lean核验。
在 ,红色锁点候选为 ,紫色直接求值为14,蓝色统一公式保证至少2;三者使用相同基线。 的C.2下界已经超过已核参考包络25;锁点探索尚未超过我们自己的C.2结果,且无成功完整新证书,图中不加入红点。两侧纵轴刻度独立,不能用曲线的视觉高低或交点判断数值反超。共同基线的完整核验
C.2接受预算分别为4646与9563,故相应 下界再加一。原始严格接受证书及下一预算的全参数排除均已独立复算;本次只将已有数值加入主图。原始数值报告 · 独立数值核验 · 本次绘图数据
一般段在 保证至少增加2、3、4、6、9,并在 分别保证至少增加13、2,346、152,837,269;这些是保守下限,非精确增量。对每个 , 正是正文所列五项明确参考界的最大值,因此蓝色曲线给出的也是新下界超过这一参考包络的保证增益。蓝线从12连续显示至64,同一解析定理覆盖全部 ;统一定理对全部 已完成端到端Lean形式证明,蓝色实线覆盖相同范围。
小参数:逐项提高具体整数
小参数数值图。 纵轴除以共同的指数因子 ,点旁数字仍为原始下界。灰点使用与差值主图相同的 , 依次为32、64、128、263、538、1085、2245、4633、9539。紫色菱形在12、13标出加强判据下界4647、9564;红色空心点保留12的锁点候选4664。前五项来自 Grill–Linzmayer,Theorem 1,v3第7页,后四项为本文精确 RS 组合预算加一;其他参考式不超过这些值的证明与全参数核验证书见共同基线报告。 来自 Östergård(2014)。
小参数的证明状态: 有完整自然语言候选与局部证书,完整Lean尚未闭合;已完成Lean的五元下界为34。 采用合作者证明稿与既有局部证书。原始材料与完整范围
六元当前为 :完整证明覆盖27–44点的全部实际分支,已完成完整参数域核对和独立概率复算,原超图染色接口已经闭合,尚无本参数Lean。完整证明 · 离线阅读页 · 独立核验范围 · 跨模型审阅范围
八元当前为 ,九元当前为 。两项均有完整计算机辅助证明,分别覆盖47–120点、57–195点;全部2094型、3450型已由独立参数域重建和不同的下降阶乘注入概率实现复算通过,全部严格小于一。两项尚无本参数Lean,独立计算与跨模型审阅的范围分别记录。八元证明 · 八元独立核验 · 九元证明 · 九元独立核验 · 八/九元完整离线阅读页 · 联合审阅与验收
七元当前为 :完整候选的424型及全部2,115,296个共同坏对整数向量已独立复算通过,尚未进行七元跨模型审阅或Lean核验。七元证明及验证范围 · 七元独立复算
十二元当前展示更新为 (相对4633增31)。新候选证明覆盖91–782点全部692个必要点数、664355个必要参数实例;独立程序重建完整参数域及全部迹重数/共度,并对20个边界实例用Fraction精确复算通过。独立检查没有第二次全量重算概率值。本次保持完整计算机辅助证明候选、无Lean;Grok已有效静态审阅新覆盖链,未发现实质问题;没有运行程序。审阅范围与处置。当前完整证明 · 完整计算汇总 · 独立核验范围
此前 (增28)的691429型证书、31型Fraction边界核验及3348个零/一锁型独立算术检查继续保留,属于旧实例证据,不作为新4664候选的全量第二算术复算。旧实例阅读页 · 旧证书报告 · 旧独立核验范围
小参数图的逐项结果使用空心点,加强判据求值使用紫色菱形;蓝色实线属于对全部 已形式化的同一统一定理。
展开:每个小参数的数值与比较来源
历史 GL 公式口径仍保留如下,仅用于对应此前展示。它们来自同文 §2式(7),v3第4页 的严格有理代入,是可行公式基线,不是原文报告纪录,也不是本次共同参考包络。
原历史数据不覆盖,见小参数历史来源。本次绘图由共同基线 JSON显式覆盖灰点与增益;2026-10-29更新数据更新六、七、八、九、十二元的新值与证明状态,不改参考包络; 的新值读取2026-10-29完整证书汇总,C.2的12、13点从原始数值证书派生并检查独立复算PASS,蓝线保留原统一公式数据。
展开:12–16与同一统一定理的连接
下表只使用统一增益公式的保守值,与蓝线完全一致;不混入红色锁点实例。旧基线为 ,新下界为 。
五点绘图数据由保存的精确证书派生,并经独立数值重算。更强C.2数值表列出14、25、45、79、116的直接增益;其中12、13的14与25现以紫色菱形直接展示在主图,与红色逐项结果共读左轴,仍不混入同一统一公式的蓝线。
一般参数:统一增加可核验的整数
差值主图的蓝色曲线展示以下主定理所保证的增益:
为绘图,对每个显示的整数 保存一个严格通过旧判据的预算 ,再取经定向舍入验证的整数 。蓝色曲线画 ,因此它也是相对真正基线 的保证增益;没有把数值寻优冒充最大预算 的求值。
主定理C与五项参考包络比较的同一解析证明现已延至全部 :在这整个范围内,新下界超过所列五项明确参考界的最大值。12–16与17起使用同一个增益公式,增长主定理的端到端Lean范围已统一至 ;五项参考包络比较仍为纸面证明,图中具体数值由独立精确程序验证。一般定理的证明不依赖图中有限采样点;这些点只给出可复算的数值展示。17起的数值见证与验证方法 · 12起的统一解析证明 · 12起的Lean核验报告
展开:绝对下界总览(对数刻度)
绝对值参考图。 纵轴为 的下界。一般段显示 与 ,即旧判据和新定理的可验取值;新旧总量在此尺度上几乎重合。黑色菱形表示 ;小参数灰点使用同一共同包络,空心点延至12并包含锁点候选4664;紫色菱形另展示12、13的C.2下界4647、9564,范围及证明状态见上文。一般段从12接起,实线属于同一已形式化的统一定理;箭头表示它继续适用于更大整数参数。
下载整组矢量图 PDF · 差值主图 SVG · 小参数 SVG · 绝对值参考 SVG
基本定义与文献基线
定义(超图与Property B)。 有限简单 元超图是 ,其中 有限,。若存在 使每条边均含两色,则称 具有 Property B。 表示不具有 Property B 的此类超图的最少边数。全文 为自然对数。
定义(RS组合判据的整数预算)。 对整数 ,令
并定义
这个判据组合了 Radhakrishnan–Srinivasan,Claim A.1,作者稿第26–27页的正关联端项,以及 Claim 2.4的证明,第7页的未编号积分,再使用有向单交边对数至多 。最大整数预算 是本文据此定义的函数,原文没有直接定义这一记号或最大化量。 两项估计在同一算法中的组合见引理1;最大值非空、有限及 的证明见引理B.4。
主定理:增长的整数增益
定理C。 设整数 ,并令
则 。对任意有限集合 和任意 ,若
则存在 ,使每条 满足 。因此
证明。 引理B.4给出最大预算及其严格参数见证。引理C.1与推论C.2在同一最小顶点反例上削减有向单交对数;引理B.1的参数控制保证该削减吸收新增的 条边。全部不等式及原超图染色结论的推导见下文定理C的完整证明。∎
旧组合判据本身给出 。定理C在整个 范围将该下界增加 ;它不改变领先的渐近阶。对全部 的五项明确参考包络比较见定理D,对 的指定零锁必要数据测试方案的比较见定理E。
文献下界与本文结果对照
以下统一使用 表示不可二染的有限简单 元超图的最少边数。为便于比较,记
论文原文给出的下界
表中严格实数界 对应整数界 。RS与CK的渐近结论没有在这里指定统一的有限起点;本文的改进是精确有限预算之上的加性整数增益;该加性项不改变 基线的领先渐近项。
同一有限参数下的精确比较
下面各 都是本文从所引分析定义的最大整数可染预算,对应 的下界为 ;这些记号及最大化约定不冒充原论文的定义。令 、,、,并令
这些支配关系的证明见引理D.2、引理D.3。因此对所有 ,上述五项明确下界的最大值恰为
而本文得到
这是定理D中已证明的逐参数比较。GL的小参数多锁定理保留其原范围;对 的指定零锁必要数据方案,另有定理E的比较。主定理C已完成全部 的端到端Lean形式证明。比较D、E仍由正文的完整纸面证明支撑。
三个保守的增益例子
只用后文证明的 ,便得到以下增益下限;这里没有计算 本身。
这些数字采用整数与有理数保守估计,帮助理解增益规模;整个参数范围的证明在下文,不由这些例子外推。
证明依赖
以下依次证明概率引理、最小反例结构、最大预算的良定性和整数增益。图中每个结点均对应正文中的已编号结果;点对覆盖和团界是证明内部推出的结论,不是主定理对原超图的附加假设。
引理1实际重染失败上界
+引理2、3、C.1最小反例与单交团
→推论C.2结构加强的可染判据
+引理B.1、B.4参数控制与最大预算
→定理C统一的正整数增益
一、一般二染色判据与完整原图连接
定义1:超图、二染色与单交边对
设 为整数。有限简单 元超图是二元组 ,其中 为有限集合, 为集合;因而每条边有恰好 个顶点,且没有重复边。记 、。
若存在染色 ,使每条边 都满足
则称 具有 Property B。记 为不具有 Property B 的有限简单 元超图的最小边数。此最小值存在:顶点数为 的完全 元超图在任意二染色中都有至少 个同色顶点,故不具有 Property B。
定义实际有向单交边对集合及其大小为
其中 与 分别计数。定义单交图 为以 为顶点集的简单图,两条不同原边在 中相邻,当且仅当它们恰交一点。
定义2:解析量与结构上界
对整数 、实数 及整数 ,定义
以及
这里 、,且 。
定义3:随机重染过程及必要事件
给定有限简单 元超图 和 。各顶点 独立选初始颜色 ,两色各以概率 出现;独立选资格位 及时刻 。以上全部随机量相互独立。
按时刻递增处理每个顶点一次。处理 时,若 ,且存在含 的边 在初态为单色、截至处理 前仍全部保持该初始颜色,则翻转 ;否则保持颜色。记最终染色为 ,失败事件为
时刻互异以概率 成立;碰撞时按预先固定的顶点次序处理,不影响下列概率。该过程为 Radhakrishnan–Srinivasan 的延迟重染算法,见 RS2000, §2 “Slow recoloring”, 作者稿第4页 “The Algorithm”。
定义初态残留事件
对 、 和目标颜色 ,定义必要事件 为以下条件同时成立:
- 初始全为颜色 ,且 ;
- 对所有 ,若 ,则 且 ;
- 对所有 ,若 ,则 。
此事件仅规定初态、资格位和次序条件;其定义不要求 最终单色,也不要求算法实际以 触发 的翻转。
引理1.1:独立 Bernoulli 变量的正关联
设 为相互独立的 Bernoulli 变量,其参数可分别取 中的任意值。若实函数 均关于各坐标单调不减,则
因此,对任意有限个关于这些坐标递增的事件 ,有
证明。 对坐标数 归纳。 时两函数均为常数,结论为等式。设结论对 个坐标成立,并以 表示最后一位取 的概率。全协方差公式给出
第一项由归纳假设非负。令 、 分别为将最后一位固定为 后对其余坐标取期望的值;单调性给出 、,故第二项等于
这证明两函数的结论。取事件指示函数即得两个递增事件的正关联;由于递增事件的交仍递增,再对事件个数归纳得到有限交结论。∎
这是独立乘积测度下正关联的自含证明;RS2000, Appendix A, Claim A.1 的证明,作者稿第26页以 FKG 不等式调用这一事实。
引理1.2:初态残留概率
设 、,且 为实际边数 的有限简单 元超图。对定义3的随机过程,至少一条边初始单色且最终保持其初始单色颜色,当且仅当 发生。并且
证明。 每个顶点至多翻转一次。因此,初始为颜色 的边最终仍全为 ,当且仅当它没有顶点翻转。若它的全部资格位为零,便没有顶点翻转。反之,若它存在有资格顶点而最终没有顶点翻转,则其中最早的有资格顶点被处理时,这条边仍全为原色,因而触发翻转,矛盾。这证明所述事件等价。
条件于初始染色,记初始单色边数为 。对每条初始单色边 ,事件 是资格位的递增事件,且其条件概率为 。由引理1.1,
每条 元边初始单色的概率为 ,故 。因 ,函数 为凸函数; 时它为常函数。Jensen 不等式于是给出
取补事件即得结论。∎
此估计及其正关联、Jensen 证明见 RS2000, Appendix A, Claim A.1,作者稿第26–27页。其中原文式(31)是条件平均等式,Claim A.1 的最终概率上界使用正关联与 Jensen;这里保留该上界未作线性放宽的形式。
引理1.3:新单色边的必要单交事件
设 、,且 为有限简单 元超图。对定义3的过程,以概率 有
此外,每个 和 均满足
证明。 先限制到所有时刻互异的概率 事件。若 最终全为 ,且初态也全为 ,则由引理1.2得到 。否则,在 中初始为 的非空顶点集中,选取处理最晚者 。这些顶点最终均为 ,故均已翻转。 翻转时,有一条含 的触发边 ,它初始全为 ,且直到当时仍全为 。
若还存在 ,则 初始为 、最终为 ,所以必须在 之前翻转;这与 在处理 时仍保持初始单色矛盾。因此 。因为 ,这又蕴含 。
翻转需要 。 中所有初始为 的顶点都在 之前翻转,故均有资格且时刻小于 。对 中任一有资格顶点 ,若 ,则由于 在处理 前未有顶点翻转, 被处理时便会由 触发翻转,矛盾。因此 。这些正是 的全部条件,覆盖关系得证。这一论证也覆盖 初态全为 、最终全为 的情形。
再固定单交对 及交点 ,条件于 。对每个 ,规定 恰为该集合中初始颜色为 的顶点集,同时规定 初始全为 。因 ,此初态配置的概率为 。其余资格及次序条件分别发生于互不相交的顶点集: 有资格的概率为 ;每个 有资格且早于 的概率为 ;每个 不同时满足有资格和早于 的概率为 。故相应联合概率为
不同 的初始配置互斥。对 求和、再对 积分,得到
最后一步使用换元 。∎
必要事件的单交归约见 RS2000, §2.1, Lemma 2.1 与 Claims 2.1–2.3,作者稿第5–6页;精确积分见 RS2000, Claim 2.4 的证明,作者稿第7页未编号积分式。原文在该积分之后才进一步放宽概率;这里直接保留积分。
引理1:完整RS上界
设 为整数、, 为实际边数 的有限简单 元超图。则定义3的实际重染失败概率满足
证明。 对引理1.3的覆盖关系使用并界,再代入引理1.2及引理1.3的概率式,得
而 ,故得式(1)。∎
引理1将 RS2000, Appendix A, Claim A.1 的残留估计与 RS2000, Claim 2.4 的证明中的精确积分作用于同一实际算法,并保留实际有向单交对数。式(1)是这些估计的组合,不是对原文某一条定理的逐字转述。
引理2:最小顶点反例覆盖
设整数 、。若存在边数至多 的非 Property B 有限简单 元超图,则其中存在顶点数最少的反例 。对任一这样的 ,记 、,则 、,任意两个不同顶点都同处于至少一条边,且
此约化见 Grill–Linzmayer,§1,式(3)前的Goldberg–Russell论证。
证明。 有限顶点数的非空集合有最小值,故可选取所述 。没有边的超图具有 Property B,因此 ,继而 。
若两个不同顶点 从未同处一条边,将它们合并,其他顶点不变。每条原边的像仍有恰好 个顶点;以这些像边组成集合得到简单 元超图,其边数不超过 。若像超图具有 Property B,将其染色沿合并映射拉回,便使每条原边同时含两色,违背 为反例。因此像超图仍为边数至多 的反例,却比 少一个顶点,矛盾。
于是每对不同顶点至少同处一条边。计数所有“顶点对包含于边”的关联,得 。解关于 的二次不等式并利用 为整数,即得 。∎
引理3.1:由团数控制图的边数
设 为有 个顶点的有限简单图。若其每个团的大小都不超过实数 ,则
证明。 令 为 的补图,记 的顶点度数为 。均匀随机排列全部顶点,并选取早于自身全部 邻居的顶点。若两个所选顶点在 中相邻,则它们各自都须早于对方,矛盾;故所选集合在 中独立,在 中为团,其大小至多 。
顶点 被选中的概率为 。取期望,再用 Cauchy–Schwarz 不等式,得到
因为 ,整理即得结论。∎
此为 Turán 团数上界所对应的边数不等式;上面的随机排列证明不需要精确 Turán 数或等号情形的分类。
引理3:Gram矩阵与单交图界
设 ,且 为实际边数 、顶点数 的有限简单 元超图。则 的每个团大小至多 ,且
若此外 且 是引理2中的最小顶点反例,则
证明。 取 中任一 点团,即取 条两两恰交一点的不同原边。令 为这些边的 关联矩阵,行对应所选边,列对应 。每行恰有 个 ,不同两行的内积为 ,故
其中 为单位矩阵, 为全一矩阵。对非零实向量 ,由于 ,有
因此 为正定矩阵,。将引理3.1用于 、,并注意 ,便得式(3)。
若 是引理2的反例,则 。因 ,式(3)给出
另一方面,按有向不同边对计数,总有 。对这两个上界取最小值即为式(4)。∎
定理A:无附加结构假设的充分判据
设整数 、。若存在实数 满足
则任意边数至多 的有限简单 元超图均具有 Property B。因此 。
证明。 没有边的超图具有 Property B。若结论不成立,由引理2可取顶点数最少的反例 ,其实际边数满足 。将引理1用于这个 。因为 且 ,有
再由引理3的式(4)、 以及假设(A),实际失败概率满足
所以补事件 有正概率,存在一个随机结果使最终染色中没有单色边。其最终染色为 的合法二染色,与 为反例矛盾。因此所有边数至多 的原始超图均具有 Property B。根据 的定义,。∎
参考文献
[RS2000] Jaikumar Radhakrishnan and Aravind Srinivasan. Improved bounds and algorithms for hypergraph 2-coloring. Random Structures & Algorithms 16(1) (2000), 4–32. DOI;作者稿;本地副本:ref/radhakrishnan_srinivasan_2000_two_coloring.pdf。本文的章节、命题编号及具体页码均按该作者稿标注。
二、旧预算的有限性与统一加一余量
定义B.1:精确接受集合与预算
给定整数 ,令 ,并对 定义
定义整数接受集合
此判据由 引理1 的实际重染失败上界和有向单交对数 得到。其概率分析来自 Radhakrishnan–Srinivasan 作者稿:第4页第2节给出延迟重染算法,第6页给出 Claim 2.4,第7页其证明中的未编号式给出所用精确积分,第26–27页附录A的 Claim A.1 给出正关联与 Jensen 估计。本文组合这些估计、保留精确积分并采用 的有向对计数,定义 及下述预算;原文不逐字包含这一预算量。
引理B.4将证明 非空且有限,因此下式良定:
引理B.1:接受参数的控制
设 为整数, 且 。设 是接受不等式的见证,记 、、。则
证明。 因为 ,所以 、。接受不等式给出
当 时,接受不等式两边同为零,因此 ,从而 。若 ,则对 ,Bernoulli 不等式给出
因此 。又由 Bernoulli 不等式有 ,故 (3) 蕴含
矛盾。这里使用了 及 。所以 。在区间 上使用同一被积函数下界,得到
由于 ,后一严格不等式一方面给出 ,另一方面可以取对数。因此
∎
引理B.2:统一增长比较
对所有实数 ,有
此外,若 、 均为整数,,,则 ,并且
证明。 先验证 (5) 的起点。由
得到 。又 ,故在 时,(5) 左边大于 ,右边小于 。由
可得比值 的对数导数满足
所以 (5) 对全部 成立。
根据 的定义, 蕴含 ,且
最后一个不等式使用 、 以及 。又由 和 (5) 得到 ;将其除以 ,即得 (6)。∎
引理B.3:接受预算的加一转换
设 为整数, 且 。则任意边数至多 的有限简单 元超图均具有 Property B。
证明。 取 的一个接受见证 ,沿用引理B.1中的 。令 、,并置
由 、 的适用情形,结合引理B.2的 (6) 及引理B.1的 (4),得到
第二步使用 。所有对数均有定义,因为 、、。于是
将此式与 的接受不等式相乘,得到
引理B.1给出 ,所以该不等式满足定理A对参数的要求,并且正是定理A在预算 的充分条件。因此任意至多 边的原始超图均可二染。∎
引理B.4:接受集合的有限最大值
对每个整数 ,集合 非空且有限,含有 ,且其每个元素均小于 。因此 存在,满足 ,并且该最大整数本身有一个接受见证 。
证明。 取 、。由二项式展开的前三项,
故 ,即 。又 ,因此
这证明 。若 且 ,引理B.1给出 ,即 ;若 ,同一上界也成立。因此 是非空有限整数集合,必有最大元。最大元属于 ,故有实际见证;由引理B.1,该见证满足 。这里无需假定任何连续参数优化问题的最优值可达。∎
定理B:统一加一增益
对每个整数 ,式 (1) 定义的预算满足
等价地,任意有限简单 元超图,只要边数至多 ,就具有 Property B;此结论不附加顶点数、点对覆盖、度数、共度或线性条件。
证明。 引理B.4保证 、,并给出 (2) 中预算的上下界。将引理B.3用于 ,即得所有至多 边的原始超图均可二染。因此不可二染超图至少有 条边。∎
精确性与比较范围
积分是显式有理系数多项式:
令 。接受判据等价于 ,因而是 上有理多项式的严格正性问题。引理B.4将候选整数 限制在有限区间内;定义及统一证明均不依赖浮点搜索。
对任何 ,CORE引理1配合 ,直接给出任意至多 边的原始超图均可二染。因此式 (1) 的判据给出的整数下界为 ,定理B将它在整个 范围至少提高一。其他参考函数及指定离散位置/度共度测试方案的比较见 BASELINE_COMPARISON.md,其范围由各自定理陈述。
三、公共点二分与增长的整数增益
引理C.1:单交团的公共点二分
设整数 、、, 为大小 的有限集合, 为互异的 元集合,且对所有 有 。则:
因此,对任意 点简单 元超图 ,有
证明。 若存在公共点 ,两两单交保证 互不相交。因此所有边的并集恰有 个顶点,得到第一个结论;这也包括 的情形。
若没有公共点,固定一条边 。对每个 ,存在族中一条不含 的边 。设 是族中含 的边数。这些边与 的交点两两不同:若两条含 的边在 上有同一交点 ,则因 而 ,这两条边便至少交于 两点,违背假设。故 。每条不同于 的边恰交 一点,因而
这给出第二个结论。最后,将二分应用于 的任意非空团,即得所述团数上界;若 无边,其单交图的团数为零,上界仍成立。∎
推论C.2:加强的无结构二染色判据
设整数 、。定义
以及
若存在 满足
则任意边数至多 的有限简单 元超图均具有 Property B。因此 。结论不附加顶点数、点对覆盖、度数、共度或线性假设。
证明。 因 ,有 ;又 ,故 ,定义中的分母均非零。
若结论不成立,按CORE引理2选取边数至多 的最小顶点反例 ,记实际顶点数为 、边数为 。该引理给出 。CORE引理3的关联矩阵论证给出 ,引理C.1则给出另一团数上界。结合这两个界及右端对 的单调性,得到
为将此界转为有向单交对数的上界,令 为 的补图,顶点度数记为 。引理3.1中随机排列选独立集的论证及 Cauchy–Schwarz 不等式给出
由 ,可得
再结合 及 ,得到 。将这一上界代入CORE引理1,并使用 、,实际失败概率至多为
于是存在合法二染色,与 是反例矛盾。∎
定理C:增长的整数增益
设整数 ,并以定义B.1定义 。置
则 ,且任意边数至多 的有限简单 元超图均具有 Property B。因此
证明。 先证明对任意整数 、,都可在同一个接受参数下增加
条边。取接受见证 ,记 、、、,并令 、。引理B.1保证 、,且
先控制 的范围。由
可得 ;对于实数 ,比值 的对数导数满足
在起点12,该比值大于 。结合 ,得到 。又因 且 ,有 ,从而 。
接着控制 。对实数 ,
由起点 ,得到
根据 的定义,有 、,故
最后一步使用 及 。因此,推论C.2中定义的 满足
由 及 的定义,有统一严格余量
再由初等对数不等式 、 的适用情形,
第二行使用 ;第三行使用上述严格余量;第四行使用引理B.1及 。所有对数均有定义,因为 、、。因此
与 的同一个接受见证的不等式相乘,得到
推论C.2的参数条件 、、 均已满足,故任意至多 边的原始有限简单 元超图均可二染。该推论在内部选取最小顶点反例,证明其点对覆盖,并将同一实际单交图的团数界转为实际重染失败概率小于1;这些结构均不是原始超图的附加假设。
最后,引理B.4给出 及 ;取 ,便得到 以及所述染色结论和整数下界。∎
引理C.1是线性交族的自含团界。其公共点二分只用于约束同一实际超图的单交团,不要求将全部团划为两种全局结构。定理C始终保留同一个接受见证 ,用有向单交对数的削减吸收新增的 条边。与其他明确参考界的比较见 BASELINE_COMPARISON.md。
四、参考界与有限测试方案的完整比较
定义D.1:参考预算与参考包络
本节固定整数 。超图、Property B及 沿用定义1;本节的所有全域染色结论均量化任意有限简单 元超图。
令 、,并记
沿用前文的整数预算
式(B1)是本文定义的预算函数:将 RS2000,Claim A.1、式(31),作者稿第26–27页的正关联端项,与 RS2000,Claim 2.4的证明,第7页未编号积分组合,并对有向单交边对使用 。完整组合由本文引理1证明;原文没有定义同名的 。定义B.1及引理B.4已证明其良定性,并给出
为固定比较对象,再定义:
本节的参考包络明确取为
这里每个 是可染边数预算,下界要再加一; 本身已经是 的下界。所有最大值的存在性将在比较中一并得到。
定理D:参考包络比较
对每个整数 ,定义D.1的参考包络满足
因此,前文增长增益定理在此范围给出
其中式(B4)的整数增益 满足 。
证明。 由引理D.2,;由引理B.4,。引理D.3证明其余三个预算均不超过 。代入定义D.1的式(B2),即得(B3)。再由定理C的增长整数增益结论,得到(B4)。∎
比较范围。 Grill已发表的锁点数值定理适用于 ,不提供本节 的另一条完整数值函数。其固定 的Catalan结论也不能单独加入全超图包络作为同值下界。RS/CK的渐近常数结论,对每个固定 在充分大 成立;本节用准确有限判据比较,不把未知起点或端点常数冒用为逐 数值。
定理E另证明:对 ,一个明确列出测试项目的Grill零锁必要数据松弛方案,不能接受任何 。这是对该有限测试方案的补充比较,不将全部可能的真实结构推理或多锁扩展混入(B2)。
引理D.1:覆盖与平衡染色下界
设整数 。对整数 ,置
则
该公式见 GL2024,式(3)–(5);以下给出其全域形式的证明。
证明。 若存在非B超图,在边数不增加的反例中取顶点数最少者。前文的合并点归约保证它覆盖每个点对。因此每点度至少 ;按关联总数计数,边数 至少为 。
在同一 点超图上,均匀抽取大小为 的红色类。每条指定边单色的概率是 。非B意味着每份这样的染色都有单色边,所以期望单色边数 ,即 。此处不能在 为整数时多加一。两种必要条件作用于同一个实际反例,随后取 的最小值即得(B5)。 时可将两色类均取少于 点,直接可染,故无遗漏。∎
引理D.2:覆盖与平衡包络的统一上界
若整数 ,则 。
证明。 取
先证明 。两个奇偶起点分别是
令 。对整数 ,
因为分子减分母等于 。分别从12和13以步长2归纳,便得到全部整数 的 ;特别地, 是式(B5)的合法输入。这一归纳不需要逐个参数枚举。
又有 ,从而
还要上界同一个 的 。令 、。对 和 ,
因此单色概率 满足
这里 Bernoulli 不等式适用,因为 ;最后的严格不等式使用 。所以 ,且 。与(B6)合用得到(B3)的第一式。这是选择一个 上界外层最小值,不是断言所有 的max项都不超过 。∎
引理D.3:其余参考预算的支配关系
若整数 ,则定义D.1中的三个最大整数预算均存在,并满足
证明。 GL2024,§2,式(6)的连续上界在本文记作
对 ,第二端点项不小于第一项;坏对项与第一项的比值 随 非增。因此两项至多交换一次,允许交换点在端点。令交换位置为 并积分,得到准确恒等式
对 、,Bernoulli凸性不等式给
代入 ,可见(B1)的失败上界不大于同一 的(B8)表达式(取 );又 且 ,故(B1)也不大于线性判据。于是任何 被连续或线性判据接受,都会被(B1)接受。较小的 已低于 。这证明
连续min逐点不大于坏对项,故 ,进而 。这些集合非空:当 时,坏对项及连续min均为零;线性判据取 时等于 。又因每个被接受的整数均不超过有限的 ,三个集合的最大值均存在。故上述三个预算均有定义,且满足本引理的支配关系。∎
定义D.2:零锁必要数据测试方案
固定整数 、。定义如下必要数据松弛方案:它遍历整数 及下列有限数据; 已使 的范围有限。
选一个标号中心0,给出整数度 、中心共度 ()和最大共度参数 。只保留下述测试均通过的数据:
- ,;所有度至少为 ,并有 。
- ,;,对 有 ,并有 。
- 对每个 ,令 ,要求
- 覆盖点对的标量条件 。
这些是标量与逐行容量测试,没有要求存在一张同时满足全部行和的对称共度矩阵,也没有要求存在实际边族。实际非B输入不能有度为 的点,否则将该点染红、其余点染蓝即proper;所以第1项未丢掉非B对象。下文仅在 ()的子域构造不通过数据,不把这项等式作为一般原H的必要条件。
对这样的数据,记 ,使用 GL2024,§2,第5页式(9)之后的两条未编号不等式给出的两条上界
测试方案仅在每份保留数据均满足至少一个充分条件时接受 :平衡染色联合上界 严格小于1,或下列离散式严格小于1。后者是 GL2024,§2,式(8)的零锁形式:
不可能的二项式取零。该方案只比较(B9)、两条指定 公式及上述数据测试;不包含实际边族可实现性、edge-critical结构、完整真实共度或任意多锁推理。
定理E:指定零锁测试方案的预算限制
对每个整数 、每个整数 ,存在通过全部上述测试的数据,其平衡联合上界大于1,且 。因此该明确的“全部松弛数据均须通过”方案不能接受任何这样的固定 。
证明。 引理E.1构造通过定义D.2全部数据测试的输入,并证明其平衡联合上界大于1以及 。因 ,有 。若 ,引理E.3给出 ;若 ,引理E.4给出相同结论。式(B9)关于第三个参数非减,故 。这份保留输入使两项充分条件均不通过,定义D.2的方案因而不接受 。∎
引理E.1:满足全部数据测试的输入
设整数 、。令 、、、。则存在定义D.2保留的一份数据,其平衡染色联合上界大于1,且存在实数 满足
证明。 按上述记号取
先记一个全范围余量:对所有实数 ,
因为 的导数大于 ,而在256有 。由 得 ;特别 且 。
将 均分为 个尽量相等的整数 ,将 独立均分为 个尽量相等的整数 。取
两个均分的向上取整重数分别选择以保持各自精确总和,不要求二者的余数位置相同。总度为
以下取整范围用于核全部测试:
第一式由 得到。令 。的均值大于 ,至少超过 达 ,所以向下取整仍不小于 。另一方面 ,故 ;同理
这些不等式在 、 下均有严格余量。于是所有非中心度不超过 ;中心度 ,且 。又 ,所以中心共度的范围测试通过。
由于 ,所有度均不小于 ;总度等式给 ,故 。粗点对覆盖式也由 直接得到。
普通点的目标共度行和为
其下界 。其上界 ,而
所以逐行上限也通过。总行和
为偶数,因两个系数都是相邻整数之积。普通点的 在已指定的中心共度 中达到;中心参数为 。
令 是一条指定边在均匀平衡染色下单色的概率。引理D.2证明中的平衡单色概率乘积估计给
因为 、。因此平衡染色联合界不排除这份数据。这是充分判据的数值不通过,不是实际染色失败概率的下界。
记
两条旧公式满足 ,而
因此 。还由 得
以上证明了所构造数据的全部测试条件及断言的两个数值界。∎
引理E.2:离散位置式与连续积分的比较
设整数 、、,实数 ,并令 、、。定义
则式(B9)所定义的 满足
证明。 关于 对称,在 非减,所以总变差至多 。沿用
在(B9)中只保留 ,令 ,便有 。两个分子降阶乘的最小因子分别为 、;分母降阶乘均至多 。端项因此有 因子、坏对项有 因子;再用 ,每个保留位置的最小项至少为 。
总变差的黎曼和估计给
于是得到关于实际离散式的代数下界
这证明了断言,且保留了式(B9)的 因子及离散位置偏移。∎
引理E.3:中间预算区间的严格下界
在引理E.1的假设和构造下,若 ,则 。
证明。 取 、,并按引理E.2定义相应的 ,即 、、。由(B8),
括号内的导数为 。若 ,最小点是 ,。否则,由 得 ,所以唯一最小点在内部且
最后一个非严格比较可由 及 得到。令 ;由 ,
对 、,
时等号成立;固定 ,令 ,则关于 的导数 。端点由连续性处理。
记
由 的定义,对同一个 有 。因此
这里用(B13)、、和 。若 ,、,故同一较弱估计仍成立。
又 、。由 ,(B14)给
结合(B16)及 ,
最后由(B10),;而 ,两个损失的和严格小于 ,故断言成立。∎
引理E.4:大预算区间的严格下界
在引理E.1的假设和构造下,若 ,则 。
证明。 令 ,并按引理E.2取 ,记相应积分与中点值为 、。由(B13),,由(B8),函数 的导数为 ,故其最小值在 取得,得到 。又 。直接由(B14),
倒数第二步使用 与 。故本区间的严格下界成立。∎
说明。 引理E.3所用 直接来自(B1)的最大值定义,对每个 均成立;不需要另行假设可接受预算集合下闭。
本节文献与引用位置
RS–FKG及有向坏对积分来自 Radhakrishnan–Srinivasan作者稿§2及Claim 2.4的证明(作者稿第4–7页)、附录A的Claim A.1与式(31)(作者稿第26–27页)。线性判据见 CK2015,§2,式(2.1)–(2.3),刊页409–410;其渐近结论为Theorem 1。准确排列概率见 P2009,§2.1,Claim 1及Corollary 1,作者稿第2–3页。
(B5)的可读原始陈述见 Grill–Linzmayer2024式(3)–(5),以及Aglave等2020刊页83的Lemma4.3;两者将该方法归于Goldberg–Russell。(B7)、(B9)及两条度/最大共度公式使用同一Grill原文。Goldberg–Russell作者稿的实际正文以四元情形为主,并附局部错误警示,故本节一般公式不以其未核的局部分类为进口;所需全域归约与计算已在正文自含证明。
公共点二分的恰单点交特例已由引理C.1完整证明,本节引用该引理。
原始资料的实际核对及本轮有界检索范围见最终文献核对记录。参考包络采用(B2)的明确组成;固定小 数表与固定 特例仍按其原量词使用。
参考文献与核验资料
[RS2000] J. Radhakrishnan and A. Srinivasan. Improved bounds and algorithms for hypergraph 2-coloring. Random Structures & Algorithms 16(1), 4–32, 2000. 作者稿;本地PDF。所引算法、Lemma 2.1、Claims 2.1–2.4、Claim A.1及页码均依27页作者稿,页码不冒作期刊排版页码。
[CK2015] D. D. Cherkashin and J. Kozik. A note on random greedy coloring of uniform hypergraphs. Random Structures & Algorithms 47(3), 407–413, 2015. DOI。本文引用刊版§2式(2.1)–(2.3),第409–410页。
[P2009] A. Pluhár. Greedy colorings of uniform hypergraphs. Random Structures & Algorithms 35(2), 216–221, 2009. DOI。准确排列概率见§2.1的Claim 1证明,作者稿第2–3页。
[GL2024] K. Grill and D. Linzmayer. Improved Lower Bounds for Property B. arXiv:2403.05674v3, 20 June 2024. 本文使用§1式(3)–(5)、§2式(6)–(8)以及式(9)之后两条未编号的单交对上界。
本卷组合的四个规范来源是一般充分判据、统一整数加一、团界加强与增长增益、参考界完整比较。它们保持规范地位;本页与Markdown阅读稿提供完整合并阅读。各具体引用、版本和页码的核对记录见文献定位。
本文全部整数k≥12的增长主定理C已完成端到端Lean形式证明:最大预算、至少二的统一增益、实际反例结构、概率判据和原Bool染色均已连接;独立原命题及公理审计已通过。比较定理D、E仍为本文所给的纸面证明。原RS核心与17元试点保留为前一阶段记录。
交接与验证补充:人工交接、合并数学审计、核心审阅处置、比较审阅处置。