八元与九元超图的 Property B 下界
m(8) ≥ 267,m(9) ≥ 543 · 两项完整证明与独立精确复算
目录 · 两项完整证明与通用公式
完整计算机辅助证明 · 独立全域重建与全概率复算 · 尚未 Lean
本卷给出两项针对任意有限简单超图的完整证明:
两项原始命题与验证范围
八元定理。 任意有限简单八元超图,若边数至多266,则存在使每条原边同时含红、蓝两色的染色。因此
九元定理。 任意有限简单九元超图,若边数至多542,则存在使每条原边同时含红、蓝两色的染色。因此
| 结果 | 本卷固定参考基线 | 下界增益 | 全部独立概率复算 | 内部完整点数域 |
|---|---|---|---|---|
| 263 | 4 | 2094型,另299项组件配额 | 47–120 | |
| 538 | 5 | 3450型 | 57–195 |
以下先收入通用条件排列的完整概率公式,再完整收入两份证明。两项均已完成独立全域重建和全概率复算,Grok与Gemini的整篇静态审阅均未发现实质缺口;准确范围见文末审阅记录,尚无 Lean 形式证明。
通用条件排列概率:完整公式
通用 · 2. Generic conditioned greedy bound
Take a uniformly random permutation conditioned on fixed distinct vertices
Write
A locked center cannot have its incident locked vertices in the wrong order. For a free center, both incident edge types must respect the earlier/later locked vertices. Binomial coefficients are zero when their lower argument exceeds the upper argument.
Let
The latter bounds true critical-pair probability because it replaces the number of genuinely single-intersection pairs by the number of all distinct ordered pairs in each type cell.
For a locked center
distinct unordered incident-edge pairs that share another vertex. None can be critical. For each unordered type cell
Therefore the conditional failure probability is at most
If this is below 1, the hypergraph is 2-colorable.
For no locks, the global pair surplus yields at least
unordered multi-intersection pairs. So in the no-lock stage, replace the total number of ordered critical-pair candidates
八元:完整证明
八元 · 八元超图的 Property B 下界:
主定理(完整计算机辅助证明)。 对任意有限顶点集
本稿覆盖原始完整对象域。所有选点条件均在同一实际最小反例内推出,有限计算只核验完整必要局部类型的精确有理不等式。最终2094型全部严格,最大
八元 · 1. 定义与无损归约
定义1.1。 有限简单八元超图
引理1.2。 若主定理为假,则存在同一实际反例,满足
证明。 在原始反例中选顶点数最少者。若某不同点对从不共边,将这两点识别,任一原边的像仍有八个不同点;重复像边仅保留一次。所得边数不增加,合法像染色可拉回为原染色,所以仍是反例,违背最小性。因此每个点对被覆盖。
对每点求共度和,得
若
此时
八元 · 2. 原染色算法与条件排列充分界
本节复述既有八/九元通用机制,来源为 propertyB_small_k/propertyB_k8_k9_proof.md 第2节及 propertyB_m8_certificate_v2.py 的 Calculator。机制不固定总边数265;本次全部重数之和为266。
固定不同实际锁点
引理2.1(实际失败见证)。 初始全红,按排列依次处理顶点:若当前点是一条当前全红边的最后点,将其改蓝。最终没有全红边。若有全蓝边
记 Calculator.endpoint/weight;这些公式只将每条边的大小设为本次的八。
定义
八元 · 3. 七元链接的坏对配额
引理3.1(基础链接配额)。 固定锁点
证明。 不同七集的交至多六点。对各支撑点的出现重数
引理3.2(component 支撑加强)。 对
证明。 随机次序中早于全部邻点的图点形成独立集,期望为
若支撑至多十四,每个七集至多有一个不同的不交伙伴:支撑不足十四时没有,恰十四时只有其补集。因此补图至多
不同相交分量的支撑不交。取上述所有适用支撑界的最大值
引理3.3(同一坏对向量的最大避点扣除)。 在含锁
证明。 实际坏对计数向量满足每个单项配额和全部容量,故实际目标至少每个单项最小值,也至少其最大值。没有将不同避点成本相加;每个固定位置的实际坏对只记一次。
八元 · 4. 零锁:47–82点
引理4.1。 对
证明。 令
八元 · 5. 最低度一锁:83–89点
对实际最小度
八元 · 6. 最低单位伙伴及自适应三锁:90–107点
引理6.1(实际 successive-min 选点)。 取实际最低度点
证明。
对全部
单位三锁的完整迹恰为两种:若有三点同边,则
全部72个父型的完整第三度数区间及两种迹合计508型,全部严格;最大
八元 · 7. 统一低度单位三锁:108–119点
引理7.1。 对该范围,存在三名度数至多二十、两两共度一的实际点。
证明。 令
将这三个实际点按度数排序,在
八元 · 8. 120点的全局单位十七度点
引理8.1。 120点时,可以选四名不同的实际十七度点,且它们两两共度一。
证明。 (1)给每点度至少17。若十七度点有
四个单位共度锁的全部至少二点迹恰为
全部单点迹由度17减去已有多点迹确定,空迹由266减去非空数。固定位置
八元 · 9. 原命题装配
反设存在至多266边的原始反例。引理1.2将其归到同一实际简单、点对覆盖、恰266边、47–120点的反例。第4–8节覆盖此完整区间;每支的实际选锁保证输入属于完整必要局部域,每个域的全部型均有严格概率上界,故由(2)得到实际合法染色,矛盾。
该染色染好完成后的全部266条边,因而也染好补边前的原边。最初的识别操作只用于推出最小反例的点对覆盖,并未给原输入增加点数、度数、共度、平衡染色或证书假设。主定理成立,得到
八元 · 10. 证书、复现与准确状态
| 完整实际分支 | 必要型数 | 最大精确上界 |
|---|---|---|
| 47–82零锁 | 36 | 433608879718/433637886825 |
| 83–89一锁 | 89 | 68318532492247/68457295662756 |
| 90–107直接双锁 | 795 | 47610603055191656213/47614325741405382960 |
| 72个未直接结束父型的完整三锁延展 | 508 | 788865098801232514/796148628468304293 |
| 108–119低度单位三锁 | 660 | 160893083202769161823/161038233221975713656 |
| 120四名十七度点 | 6 | 42737314248516385339/43417170721611099270 |
| 总计 | 2094 | 433608879718/433637886825 |
CERTIFICATE.json 保存全部实际迹、实际标签与布局、完整父域/第三度数范围、299个实际 component 配额和每行精确值。SUMMARY.json 为摘要。certificate.py 不再搜索布局,而按保存的成功布局重建完整域并全部重算;单次约8.437 CPU秒。
复现:
python3 context/propertyb-m8-267-20261029/certificate.py
该程序依赖本目录 component_trial.py 及既有 propertyB_small_k/propertyB_m8_certificate_v2.py,均是标准库 Python。初次布局与分流诊断保存在 INITIAL.json、COMPONENT_TRIAL.json、ADAPTIVE_TRIAL.json,它们的失败型仅是历史充分界失败,不是超图反例或最终缺口。最终证书覆盖域不依赖删除这些历史记录。
本轮记录的三次有界试算约5.187、2.761、2.861 CPU秒,最后完整固定布局重放8.437 CPU秒,合计约19.25 CPU秒;另有很小的导入/表初始化开销,未触及60 CPU秒预算。作者程序复用既有二项式核。独立检查另写下降阶乘注入核及递归组件DP,不导入作者概率或域生成模块:全部2094个分数与299项配额精确相等且严格,约9.401 CPU秒。Grok与Gemini均静态核查完整数学链和计算依据,均未执行程序;原始回应完整保留。最终数学结论是上述完整计算机辅助证明,本参数无Lean,也未宣称第二台机器复现。
九元:完整证明
九元 · 九元超图的Property B下界:m(9)≥543
九元 · 1. 命题与证明范围
主命题。 任意有限简单九元超图H=(V,E),若|E|≤542,则存在红/蓝染色,使每条原边同时含两种颜色。因此m(9)≥543;相对本任务固定参考538,增益为五。
证明状态。 完整计算机辅助证明。原始输入归约、实际选点、完整必要迹域及3450个严格有理数证书均已完成;独立实现重新生成完整决策树并复算全部分数,逐项精确相等且严格。Grok与Gemini整篇静态审阅均未发现实质缺口。验收状态为sound-modulo-imports,明确保留有限精确计算及通常软件信任;本参数尚无Lean。详见独核报告与联合审阅。
概率机制及二项式条件概率沿用合作者propertyB_k8_k9_proof.md第2节,原始实现为propertyB_m9_certificate_v2.py。本次显式使用k=9、M=542、总度4878;链接为八元集合,不沿用六元研究中的五元链接常数。
完整成功记录在[CANDIDATE.json](context/propertyb-m9-543-20261029/CANDIDATE.json),每行包括顶点数、实际度数、实际迹重数、锁位置、扣除方法及精确失败概率界。独立于阶段选择逻辑的实际域核查在[coverage.py](context/propertyb-m9-543-20261029/coverage.py)和[SUMMARY.json](context/propertyb-m9-543-20261029/SUMMARY.json)。
定义1.1。 d(x)为实际度数,
九元 · 2. 原题反例的完整必要域
引理2.1。 若主命题为假,则有同一实际不可二染的简单九元超图满足
证明。 在至多542边的反例中取顶点数最少者。如果两个点从不共边,将二者识别;每条像边仍有九个不同点,重复像边只保留一条。所得超图边数不增加,而且其合法染色可拉回原边,因此仍不可二染,违背最小性。故每个点对被覆盖。
对每个点有
v≤16时把点分成两个大小均至多八的颜色类。17≤v≤56时,均匀选⌊v/2⌋名点染红,固定九元边单色概率为
完整40项精确计算给balanced字段。
于是57≤v≤195;在此域有C(v,9)≥542,故可补入不同九元边至恰542边。补边保持不可二染和点对覆盖;以下全部度数、共度和迹针对补边后的同一实际超图。∎
九元 · 3. 条件贪心和八元链接避锁配额
引理3.1(实际失败见证)。 固定一个顶点排列,初始全部红色,按序处理当前点:若它是一条当前仍全红边的最后点则改蓝。最终无红色单色边;若有蓝色单色边B,则存在原边A,使A∩B={z},且z是A的最后点和B的最早点。
证明。 最终全红边的最后点在处理时会被改蓝,矛盾。若B全蓝,取其最早点z。它改蓝时有一条仍全红、在z结束的边A,故A除z外全在前,B除z外全在后,交点唯一。∎
固定不同实际锁点
全部不同原边对赋非负单交记账权,实际非单交对不会成为失败见证。锁位置若有不超过该位置实际非单交对总记账权的扣除
是实际失败概率上界。三个局部上界分别来自结束边、开始边、实际单交见证的并集界,再对位置取并集界。严格U<1意味着有限条件排列空间中存在一次成功排列,其输出是当前实际全部边的合法染色。
引理3.2(九元避锁配额)。 固定锁j及其余锁子集R。含j且避开R的f条实际边,删去j后是支撑至多N=v−1−|R|的不同八元集合。它们相交无序对数Q满足
在含j的无序迹型胞{T,U}中,容量为C(
证明。 每点链接重数a满足a≤1+C(a,2)。按点求和再换序得8f≤N+Σ链接对|L∩L′|。原边简单,所以链接互不相同,两个不同八元集合交至多七,得到(3.2)。实际坏对同时属于其真实迹型胞并满足容量;其总权不小于每个单项配额的最小成本,也不小于这些成本的最大值。各R成本没有相加,不会重复扣除。∎
repair.py中的AvoidCalculator实现此最大扣除,完整池原语来自原Calculator。最终证书只有零、一、二及三锁,不需要新的原超图分类。
九元 · 4. 选锁与完整迹域
引理4.1(最低度单位伙伴)。 取实际最低度点x,d=d(x)。若
则其单位共度伙伴至少n人。选择其中最低度点y,e=d(y),则
若
则x,y的实际共同单位伙伴中可选最低度点z,f=d(z),满足
证明。 x的共度超额为8d−(v−1),故非单位伙伴至多该数,单位池A大小r≥n。全体点最低度为d,而A全体度至少e,故4878≥vd+r(e−d)≥vd+n(e−d)。共同池在A\{y}中,去掉y至多8e−(v−1)名非单位伙伴后仍至少t人;它们度均至少f≥e。实际度数预算给4878≥vd+n(e−d)+t(f−e),从而两式成立。三个点均是实际不同顶点,两两共度一。∎
引理4.2(高点数低度单位三锁)。 对183≤v≤195,存在三名实际度数介于
证明。 令L={d≤28},r=|L|,Z=29v−4878>0,T=234−v。在L上以共度至少二连冲突边,点x的冲突度至多8d(x)−(v−1)。外部顶点度至少29,所以
因为完整13个整数的最小差为4263(v=183)。故α(G)>2,存在三个独立点,点对覆盖使它们共度恰一。∎
引理4.3(完整实际迹)。 一锁度d时,
三单位锁的实际迹恰有两种:
证明。 单、二锁公式由实际度数与边数直接恢复。三锁每个点对仅有一条共边:若三点共边,它用尽全部三对容量;否则三对各属于一条不同边。这两种耗尽全部实际可能,剩余重数由度数与总边数确定。∎
九元 · 5. 完整决策树与精确证书
引理5.1。 对引理2.1的每个实际输入,下述有限决策树都到达一个严格U<1的实际迹型。
证明。 所有最低度域均按(2.1)从头计算;所有伙伴和第三点度数域均使用(4.1)–(4.2)。证书是以下完整分流,不能把各阶段的顶点区间误读为每个点数仅适用一种方法。
57–134点。 不取锁。点对覆盖给多交无序原边对数至少
因此实际有序单交原边对数至多542·541−2q(v)。在原稿第2节的零锁公式中代入这些新常数,78个点数全严格。
135–154点。 对每个完整实际最低度d,先取一锁、位置⌊v/2⌋。证书中287个一锁型严格(135–149的全部最低度型,以及150–153的部分型)。其余最低度型使用引理4.1选择实际最低度单位伙伴,并遍历其完整e区间。该区间每个型都有成功二锁界。154点没有一锁成功叶,全部最低度域由二锁覆盖。
155–182点。 对每个完整实际最低度d,直接使用引理4.1的全部二锁伙伴域。严格二锁型即结束;未严格的73个实际(d,e)父型位于175–182点。对每个父型,(4.2)的共同池t均正,最小115;完整第三度区间最大上端28。逐项保留f=e,…,F及引理4.3的两种完整实际三锁迹,共480型,全部严格。
183–195点。 用引理4.2选三名度至多28的单位锁,将度数非减排序,遍历
成功二锁叶总计1629型;其实际位置与扣除方法逐行记录。全体叶及精确最大值为
| 成功叶 | 完整型数 | 点数跨度 | 最大有理上界 |
|---|---|---|---|
| 零锁 | 78 | 57–134 | 106487496857099087577/106600839931609480600 |
| 一锁 | 287 | 135–153 | 1972282554392680909022596/1972426008426513683838795 |
| 二锁 | 1629 | 150–180 | 394476918471453327981799/394489458501784689243720 |
| 实际条件三锁 | 480 | 175–182 | 896688388734878356588012/904701259945736563545105 |
| 低度三单位锁 | 976 | 183–195 | 41317885902922681304309/41563621287040215236328 |
| 合计 | 3450 | 全部严格 |
这里一、二锁的点数跨度只是成功叶出现的范围;181、182的实际二锁域全部继续到条件三锁,并未遗漏。coverage.py独立于原阶段循环重建整棵决策树:先按v,d列出全部输入,再按每个实际最低度单位伙伴的e域列出子节点,若无二锁叶则按实际共同池重建所有f和两个迹。它核对叶键集合与3450行恰相等,无重复、无缺口;同时检查每行总边数542、实际度数、全部单位共度、非负迹及真实位置。完整73个父型和f上限保存在SUMMARY.json的conditional_parents字段。
每行精确概率已由Calculator(9,542)或八元链接AvoidCalculator(9,542)实际计算,所有分数均严格小于一。具体布局属于同一实际锁点的合法条件排列,选择一个成功布局不改变实际超图或迹。因此每个实际输入都到达引理3.1–3.2的合法严格充分界。∎
九元 · 6. 原命题装配
主命题的证明。 假设原命题存在反例。引理2.1给同一实际恰542边、点对覆盖的反例,顶点数在57–195。引理4.1或4.2为它选择实际锁点,真实迹属于引理4.3的完整分类。引理5.1把全部顶点数、最低度、单位伙伴和三锁迹域覆盖完毕,给一个严格失败概率上界。有限实际排列空间中必有成功排列,贪心输出是补边后超图的合法二染色,故也染好原来至多542条边,矛盾。因而主命题成立,m(9)≥543。∎
九元 · 7. 复算入口与验证状态
从项目根运行:
python3 context/propertyb-m9-543-20261029/profile.py
python3 context/propertyb-m9-543-20261029/candidate.py
python3 context/propertyb-m9-543-20261029/coverage.py
profile.py重建新参数的完整必要域和基础条件概率;candidate.py构造本证明使用的完整成功叶;coverage.py重建实际决策树与每行输入绑定。前两次实际计算分别约16.73和6.56CPU秒;全部有界数值工作连同辅助试算和最终覆盖核查约25.71CPU秒,未耗尽60秒初始预算。
作者算术复用原二项式概率原语。独立检查另写下降阶乘注入概率、避锁扣除及决策树生成,不导入作者数值或域生成模块;完整3450型全部精确相等且严格,含域重算约30.09 CPU秒。Grok与Gemini均静态核查完整数学链和计算依据,均未执行程序。此处记录本参数自身的验收,不借用六元或七元审阅状态;本参数无Lean或第二台机器复现。
独立核验、证书与复现
八元证明的47–120点完整实际参数域、全部2094型概率及299项七元链接组件配额已由另一套实现重建并精确复算;所有有理值与提交证书逐项相等,且均严格小于一。详见八元独立审阅、完整核验记录和原始精确证书。
九元证明的57–195点完整决策树已由不导入作者数值或域生成模块的实现独立重建,包括319次一锁分流测试、1702次二锁分流测试及73个实际条件三锁父型。全部3450个成功叶以具名自由顶点的下降阶乘注入计数复算,逐项精确相等且严格。详见九元独立审阅、完整核验记录和原始成功叶。
这里的“独立”指不同概率实现与完整输入域重建,不表示第二台机器复现或形式化内核认证。两项仍使用所列条件贪心数学机制及普通精确整数/有理数软件信任;完整证明已在使用处写明实际选点、迹分类和合法扣除。联合静态终审的实际范围见审阅处置,原审阅范围一并保留。
复算命令:
python3 context/propertyb-m8-267-20261029/independent/check.py
python3 context/propertyb-m9-543-20261029/independent/check.py