超立方体匹配的 Hamilton 延拓
1. Ruskey–Savage 猜想
设 为 维超立方体图,即
其中 是 Hamming 距离。记 ,并记 为偶、奇顶点集。匹配是两两不共端点的边集;对匹配 ,记
中的顶点称为自由顶点,亦称孔。Hamilton 圈是恰好经过全部顶点一次的圈。
猜想 1(Ruskey–Savage,1993). 对任意 , 的每个匹配都包含在某个 Hamilton 圈中。换言之,
超立方体的 Hamilton 圈对应循环二进制 Gray 码。因此,猜想要求在保留任意一组互不冲突的指定相邻关系的同时,排列全部 个二进制串,使相邻串只改变一位。困难在于把局部边约束与全局连通性同时满足:包含匹配的生成 2-正则子图可能有多个圈,而一般匹配也未必能在超立方体内补成完美匹配。
以下将一条边的唯一变化坐标称为它的方向,并以 表示匹配使用的方向集。
2. 文献进展
表中“延拓”均要求保留原匹配的全部边;2-factor 指覆盖全部顶点的若干个顶点不交圈。
| 年份 | 作者 | 已证明的结果 | 限制及在 中的含义 | 文献 |
|---|---|---|---|---|
| 1993 | Ruskey–Savage | 提出任意匹配的 Hamilton 圈延拓猜想 | 对全部 的任意匹配作出断言 | 原论文 |
| 2007 | Fink | 每个完美匹配可延拓为 Hamilton 圈,解决 Kreweras 猜想 | 在 中覆盖含 32 条边的完美匹配 | 作者 PDF |
| 2014 | Wang–Zhang | 、 时,可延拓为 Hamilton 圈 | 代入 ,覆盖至多 11 条边的匹配 | 论文 · DOI |
| 2019 | Fink | 任意匹配可延拓为 2-factor | 覆盖全部顶点,但可能由多个圈组成 | 作者 PDF · DOI |
| 2025(预印本 2024) | Fink–Mütze | 任意匹配可延拓为至少经过 个顶点的圈 | 不保证遍历全部顶点 | 论文 · DOI |
| 2025 预印本;2026 正式章 | Fink–Hotmar | 至多五方向的匹配可延拓为 Hamilton 圈;建立有限维到方向数的提升框架 | 在 中要求 ,不限制匹配大小 | 本文采用的 v1 · 正式章 DOI |
| 2025 | Ali–Yang–Ali–Popa–Mitu | 满足额外顶点覆盖条件的 匹配可延拓为 Hamilton 圈,并推广至六方向 | 定理 12–13 带有涉及距离为 3 的顶点对的覆盖条件;不是任意匹配结论 | 原文,定理 12–13 |
| 2025 在线 | Ali–Ali–Yang | 中每个至多含 20 条边的匹配,都可延拓为 Hamilton 圈¹ | 要求 ;公开摘要未声称覆盖全部匹配,全文尚未取得 | 公开摘要 · DOI |
| 2026(预印本 2025) | Ali–Ba–Yang | 在 中,给定异奇偶端点 ,若匹配至多含 5 条边且 ,则存在包含匹配的 Hamilton – 路 | 一般结论为 、;代入 得 5。允许两个指定端点都已覆盖 | 预印本,定理 1.3 · DOI |
¹ 此项依据公开摘要,未取得全文核查证明。
3. 我们的成果
本文通过计算辅助证明解决了 Ruskey–Savage 猜想的六维情形,并进一步得到任意维数中的六方向 Hamilton 圈延拓。 三项成果及其逻辑关系如下;证明稿的审计状态见文末。
3.1 主定理:六维自由端点路径延拓
定理 2(六维自由端点延拓,). 设 为匹配,,且 。则 存在 Hamilton – 路 ,满足
端点 必须自由, 可以已覆盖。除这些端点条件外,不限制匹配的大小、方向数或覆盖形状;由于存在自由点,自然有 。原匹配始终由超立方体边构成。
3.2 六维圈结论:解决 Ruskey–Savage 猜想的六维情形
推论 3(a)(完整六维圈延拓). 的每个匹配都包含在某个 Hamilton 圈中,即
非完美匹配取自由点 及其短邻点 ,由 得到 Hamilton – 路,再加 闭圈;完美匹配使用 Fink 的已有定理。因此,圈结论覆盖全部 ,这正是 Ruskey–Savage 猜想在 时的完整断言。
相对于 Ali–Ali–Yang 的至多 20 条边结论,本文还覆盖其范围之外的 21 至 31 条边匹配;32 条边的完美匹配情形已有 Fink 的定理,不计为本文新增贡献。21 至 31 条边中的部分子类此前也已有结果,因此这里的加强是得到不附加大小或覆盖条件的完整六维结论。
3.3 任意维数的六方向圈延拓
推论 3(b)(六方向延拓). 对任意 及匹配 ,有
这一提升使用 Fink–Hotmar 的定理 5:本文补上六维自由端点命题,将无额外覆盖限制的方向数从五推进到六。相对于 Ali–Yang–Ali–Popa–Mitu 的六方向结果,本文去掉其额外顶点覆盖条件。结合已有低维结果,Ruskey–Savage 猜想在 时成立。
与 Ali–Ba–Yang 的路径定理相比,在 且至少一个指定端点自由的共同范围内,本文去掉了其五条边的限制;但其定理允许任意 和两个已覆盖端点,故本文不包含其完整适用范围。
本文采用计算辅助证明:解析归约将定理 2 化为九个完整孔层,局部构造由有限森林及矩阵秩证书保证。新增证明的核心是五维辅助命题、十四孔的极大匹配还原与十六孔的双源转移。本文不涉及七个及以上方向的任意匹配,也不主张六方向任意两个已覆盖端点的完整路径分类。所有有限证据的原件见文末补充资料。
3.4 从自由端点路径到圈延拓的逻辑
(1)六维猜想的目标:对任意匹配找到一个圈。 六维 Ruskey–Savage 猜想要求
这个圈必须经过全部 64 个顶点,并保留匹配的全部边。圈没有指定端点,因此证明时可以自行选择辅助端点。
(2)我们建立的是一个带指定端点的路径命题。
说:
量词很重要:
- 对每个匹配 ;
- 对每个自由顶点 ;
- 对每个与 异奇偶的顶点 ,即使 已被匹配覆盖;
- 都能找到满足要求的路径。
这比“存在某条包含匹配的 Hamilton 路”强,因为我们可以事先指定符合条件的端点。
(3)非完美匹配:选择相邻端点,先得路再闭圈。 任取非完美匹配 ,可选自由顶点 ,再取 的任意邻点 。相邻保证 ,由 得到包含 的 Hamilton 路
因 ,可以加上这条边,得到
该圈经过全部 64 个顶点并保留 。由于 自由,;由于 Hamilton – 路还必须经过其余 62 个顶点, 也不可能已是该路径的一条边。因此闭圈合法,得到
(4)完美匹配:使用已有定理,补齐全部匹配。 的完美匹配有 32 条边,没有自由点,使用 Fink 的完美匹配定理 得到 Hamilton 圈。所有匹配恰好分为非完美匹配与完美匹配,两类均已处理,故
因此,“至少一个指定端点自由”是构造路径时的条件,最终的六维圈结论覆盖任意匹配,不附加自由顶点要求。
(5)任意维数的六方向结论:再应用提升框架。 Fink–Hotmar 定理 5 给出:若自由端点路径命题在 中成立,则对所有 ,至多使用 个方向的匹配都可延拓为 Hamilton 圈。取 ,得到
其构造将 分成六维子立方体。因原匹配只使用六个方向,其每条边都位于某一块内部。在各块内安排路径,再沿其余坐标连接,得到一个大圈。对于非完美匹配,只需在含自由顶点的一块中用 完成最后的指定端点连接,其余块可以从包含局部匹配的 Hamilton 圈中删去一条非匹配边而得到路径,因而不要求每块都有自由点;全局完美匹配仍使用 Fink 定理。具体拼接及奇偶性验证见第 7 节。
这两步推导各自有明确输入:完整六维圈结论由 与完美匹配定理得到;任意维数的六方向圈结论进一步使用有限维路径命题的提升框架。
4. 五维局部引理
在局部论证中,允许规定匹配属于顶点集上的完全图,但新增边必须属于超立方体。后者称为短边。局部 Hamilton 路、圈在此约定下理解:其长边只能来自规定匹配。
引理 4(森林秩判据). 设 是 个顶点的偶数阶集合。对 上的完美匹配 ,定义
这里 表示保留边标号的并。设 个合法短森林的端点配对为 。若存在 个完美匹配 ,使
则对任意 上的完美匹配 ,至少一个所选森林与 合成单圈。
证明. 完美匹配连通矩阵的秩定理给出 (Cygan–Kratsch–Nederlof)。故所选完整行张成整个行空间。任取 ,将 与 循环相配可得一个与 合成单圈的匹配,因此 对应的列非零。所选行在该列不可能全为零。展开相应森林路径即得结论。
这里的合法森林在规定匹配端点上度数为 1,在待补入的孔上度数为 2,在省略孔上度数为 0,且无圈。验证只需检查短边、度数、无环性、端点配对及有限矩阵的秩。若某个森林端点配对被强迫含边 ,则先证明实际规定匹配 不含 ,再将 在 处的两条边收缩;引理应用于少两个端点的矩阵。
有限引理 5(五维避孔圈). 对 ,设 是 中的匹配,两类孔数分别为 。给定多数类中的任意孔 ,存在包含 、恰好经过 的圈,且新增边均为短边。
此命题记为 。其有限证明使用四维路径与避孔圈分类,以及引理 4。 的非邻接孔几何有 2,700 个; 有 55 个,分成大小为 的三轨道,最后一轨道使用 1,024 阶满秩证书。完整构造与有限输入见 五维 、五维 及其所引基础引理。
引理 6. 对所有可行的 成立。
证明. 任一奇偶类中任意五点至少有 11 个邻点;该有限邻域性质由全部 个五元组核验。若 ,少数类至少有五个孔,多数类除 外至少有六个孔。由于 ,两者间存在短边。将其加入规定匹配,保持 自由,并使两类孔数各减一。重复后应用引理 5 即可。
引理 7(五维平衡孔路径). 设 为匹配,且两类孔数相等。给定自由顶点 及异奇偶顶点 ,存在包含 的 Hamilton – 路,新增边均为短边。
证明. 令 分别表示两类孔数均为 时的上述路径命题与生成圈命题。Fink 的完美匹配定理给出 ,包括完全图规定匹配、仅添加短边的形式。设 已知。
若 自由,对 应用 ,再删去 。若 ,令
的孔数为 ,多数类包含 。由引理 6 得到避开 的圈;删去 并接回 ,即得所需路径。因此 成立。取自由根及其短邻点为端点,再将所得 Hamilton 路闭合,得 。归纳完成。 时匹配为空,只需自由目标分支。
5. 六维归约与有限孔层
引理 8(孔数上界). 对任意 及 ,存在匹配 ,使
证明. 在 内将 补成包含极大的匹配 。Havel–Křivánek 的定理断言,完整 中每个包含极大的匹配至少有 24 条边(1982,定理 2)。若 的全部邻点均已覆盖,则 在完整 中极大,故 。否则,取自由邻点 ; 在完整 中极大,故 。又因 自由,。
令 表示定理 2 对恰有 个孔的匹配成立。引理 8 将问题归约为
引理 9(前层增广). 设 且 成立。平移后令 ,并写
证明 时,若 已覆盖,只需处理 独立的情形;若 自由,只需处理 独立的情形。
证明. 若 已覆盖且有短边连接 ,加入该边后应用前层。若 自由且存在孔间短边 ,加入后 至少一个仍自由,以此点为根应用前层。若该边为 ,令 ,取 的另一自由顶点 及其短邻点 。前层给出包含 的 Hamilton – 路;加 成圈,再删 。
坐标置换进一步将 规范为 ,分别代表距离 。对剩余孔几何沿一坐标切为 ,记 为 在另一侧的短邻点。构造分为三步:
- 在 侧将原跨边端口与所选自由桥源补成辅助匹配 ,利用引理 7 得到规定端点路径。
- 删去 ,接入原跨边及桥源短边 ,将产生的路径压成 侧的完全图匹配 。
- 对 应用五维平衡孔圈命题(引理 7 证明中的 )、引理 6,或精确标记的森林秩证书,再展开路径并删去编码端点的辅助边。
各模板须保证辅助边最终删除、压缩无内部圈,且所有强迫配对的避障条件对实际 成立。若所选方向没有原匹配跨边,直接使用五方向自由根路径定理。不可实现的孔几何则由 Hall 见证 排除。完整转移条件见 近乎平衡切分引理 与 强迫配对转移。
有限引理 10(完整孔层). 对每个 , 成立。
证明(计算辅助). 双孔层由近完美匹配端点定理给出。其后按 递增使用引理 9;对每一规范孔几何,证书给出上述切分构造、合法的局部森林证书,或不可实现的 Hall 见证。表中列出各层的完整证明入口及最终构造。
| 孔数 | 匹配边数 | 闭合该层的构造 | 完整证明 |
|---|---|---|---|
| 2 | 31 | 近完美匹配的自由根端点定理 | 双孔 |
| 4 | 30 | 两次坐标切分,排除唯一边界情形 | 四孔 |
| 6 | 29 | 与自由、覆盖两类目标的转移 | 六孔 |
| 8 | 28 | ;最后 50 个几何的七轨道邻域构造 | 八孔 |
| 10 | 27 | 最后 4,096 个几何分为 个互斥构造域 | 十孔 |
| 12 | 26 | 最后 235 个几何的六轨道极大匹配构造,完整局部域共 3,620,052 个输入 | 十二孔 |
| 14 | 25 | 最后 25 个几何的两轨道构造,完整局部域共 805,006 个输入 | 十四孔 |
| 16 | 24 | 最后 148 个几何分为 30 个根星形与 118 个双源切分 | 十六孔 |
| 18 | 23 | 完整十六孔归约后,80,805 个几何由 个构造或 Hall 见证覆盖 | 十八孔 |
有限验证包含两项独立义务:几何域被精确穷尽;每个几何的构造适用于实现它的任意原匹配。前者由规范化、集合划分及完整枚举验证;后者由引理 4 的全称结论或极大匹配域的逐项正证书保证。极大域的完整性由输入合法性、互异性和独立计数相等确认。每层均包括自由目标与已覆盖目标,且只调用已建立的较小孔层。表中证明及所附证书给出了上述全部验证;两个末端构造的解析论证在下一节展开。
6. 两个末端构造
6.1 十四孔:从极大匹配还原到任意匹配
最后 25 个几何分为大小 20 与 5 的两轨道。以整数表示二进制顶点,其代表为 及
沿坐标 32 切分,令 、,以及
设 。由于 为孔, 必须覆盖 ;第二轨道还必须覆盖 30。将 在原覆盖顶点诱导图中补成包含极大的 。两轨道的完整极大域分别有 291,743 和 513,263 个元素。
有限证书为每个 给出自由偶点 、、不同的 ,以及 上的短森林 :其在 处度数为 2,其余顶点处为 1,并含边 。若 ,将其改为 ,否则保持不变;记所得匹配为 。证书保证 无圈。
对实际匹配作相同的目标改接:原目标边为 时,将其换成 ,内部部分记为 。若目标跨边,则 ,实际辅助跨边始终为 。于是
确实,目标内部匹配时两次改接使用同一伙伴;目标跨边时 ,而 至多删除一条不属于 的补全边。
图 的路径端点在两奇偶类中各有 个。偶偶端点路径与奇奇端点路径等数,将二者交替连接,再插入异奇偶端点路径;若全为异奇偶路径,则一致定向后循环连接。由此得到异奇偶辅助匹配 ,使 为单圈。令
两部分端点不交,故 为匹配,且
这将极大匹配的证书还原为实际 的证书。由于 已被实际 覆盖、 不属于 ,可删去 及 ,接上全部实际或虚拟跨边,以及
得到端点位于 的路径系统。与原 合并时,度数为 2 的冲突点恰是桥源镜像;它们同奇偶,而其原匹配伙伴为异奇偶悬挂端点,故无内部圈。压缩后得到 22 个端点上的完美匹配 。
局部森林强迫配对 。这两个顶点的原内部短匹配边在压缩中原样保留,而 同奇偶,故 。五个精确标记输入各有 512 阶满秩证书,应用引理 4 的收缩形式即得 侧单圈。展开后得到 上的生成圈,含实际辅助边 。删去 ,接上 与 ,即得所需 Hamilton – 路。
上述 805,006 个局部输入及两轨道覆盖的有限证据见 十四孔末端构造。其中极大域的独立计数按未匹配奇点集 分类:其余奇点注入匹配到短邻偶点,所用偶点必须包含 ;这恰好等价于包含极大性。
6.2 十六孔:双源切分的避障
最后 148 个几何中,30 个由根星形构造处理,另 118 个归约到如下五维输入:
局部命题. 令 。对每个 上的完美匹配 ,若 且 ,则存在恰好经过 、包含 且仅新增短边的圈。
证明. 有限证书给出 256 个合法短森林,其端点配对为 。向 加入 并压缩 30、31,所得 20 端点配对 均包含 。令 ;这些行在其余 18 个端点上的连通矩阵秩为 。
给定 ,令 。设 分别是 13、21 的伙伴。由于 ,可用 代替 ,得到 18 端点匹配 。逐次收缩给出
由引理 4 选择相容行并展开森林即可。
在六维应用中,取含目标的侧 ,其孔数为四偶三奇;根 位于 。选两个偶孔作桥源 ,取 ,将原端口与 配成 。引理 7 给出包含 的 Hamilton – 路。删去 ,接上原跨边、两条源桥及标签边 ,再压缩至 。
精确几何证书保证 是保留下来的原内部边, 与源镜像同奇偶,且 。只需证明实际 避开 。若 中有非原端口,其原短匹配伙伴与源镜像异奇偶,因而在源镜像集合外;该原边在压缩后原样保留,不能形成 。压缩只将源镜像处的端点移至与 异奇偶的伙伴,故只有二者均为原端口时才可能形成 。此时设其 侧伙伴为 ,在 中规定 。从一条路径删除该边将两端分离;继续删边并添加不同的叶子不能重新连接它们。因此压缩后不含 。目标为端口时,其孤立片段接到 ,结论仍成立。
应用局部命题,展开并删除标签边 ,得到包含 的 Hamilton – 路。30 个根星形与 118 个双源几何恰好互补,故十六孔层成立;详见 双源转移及有限证书。
7. 主定理与六方向推广的证明
定理 2 的证明. 给定 ,由引理 8 取 ,使 自由且 。于是
由有限引理 10,存在包含 的 Hamilton – 路,因而也包含 。各孔层均允许 已覆盖,故补全过程不影响定理的适用性。
推论 3(a)、3(b) 的证明. 先考虑 。若 完美,应用 Fink 的定理;否则取自由顶点 及其短邻点 。由定理 2 得 Hamilton – 路,加边 即成所需圈,证明推论 3(a)。
设 。置换坐标后可设 只使用后六个方向,并写
若 完美仍应用 Fink 的定理。否则取自由顶点 ,令 为 的循环 Gray 次序,其中 ,且 位于纤维 。当 时取两个顶点的循环次序即可。
对 ,令 为 在第 个纤维的对应顶点。在该纤维取包含局部匹配的 Hamilton 圈 ,选 ,删去此边得到 Hamilton 路 。令 为 在第一纤维的对应顶点。
每次由 至 翻转后六坐标的奇偶性,而纤维间对应保持这些坐标。由于 为奇数, 在第一纤维中异奇偶。由定理 2,以自由点 为根得到包含局部匹配的 Hamilton – 路 。于是
为包含 的 Hamilton 圈。 的情形由已有五方向定理得到。
补充资料
本文为研究报告与证明正文。有限构造、完整枚举域与验证记录集中于 证明资料汇编(HTML)/Markdown;总证明入口为 P6 总装证明。计算辅助证明目前通过项目内 ARIS 同族模型审计,尚未经外部同行评议或证明助手形式化验证。