九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

凯莱图哈密顿圈问题

《群论中的 50 个公开问题》 · 问题 24 专题综述

题面每个有限群的每个连通凯莱图都有哈密顿圈吗?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

凯莱图 Cay(G, S):顶点 = 群元素,边 = «乘生成元»。罗瓦兹 1970 提出 «每个连通顶点传递图有哈密顿路»(并猜想 «多数有哈密顿圈»);其群论特例——«每个有限群的每个连通凯莱图有哈密顿圈»——即是本问题。交换群已完整解决(陈–昆波 1976:交换群的连通凯莱图(除个别平凡例外)有哈密顿圈);二面体群、多数小群验证成立;Sn 的一般生成集情形尚需新思想。

主要概念

凯莱图与 «群游» 的组合化

哈密顿圈 = «字 » 的序列 w₁, …, w|G|(每字母 ∈ S),使群元素逐个不同、最后回 1——«用 S 的字母给群元素一次性编号»。交换情形化为 «格点回路的排名»(陈–昆波的 «秩语言 »);非交换情形 «字 » 与 «元素» 的对应被 «关系» 扭曲——这是困难的根源。

顶点传递的罗瓦兹框架

罗瓦兹判定:顶点传递图的 «连通度» 与 «2-因子 » 结构给出 «路版本 » 已证(洛瓦兹 1970 的 «每个连通顶点传递图有哈密顿路 » 至今仍是公开问题本身!只有部分家族证得)。凯莱特例的 «群结构» 是唯一尚未榨干的额外信息。

主要命题与证明

命题 1(陈–昆波定理,完整骨架) 有限交换群的连通凯莱图(|S| ≥ 2、非 «退化二点 » 型)有哈密顿圈。

证明(骨架) 交换群 = 循环群的直积;凯莱图 = «广义环面»(笛卡尔积与 «圈 » 的组合)。构造经 «字典式提升 »:先在 «商 »(删一个生成元)中找哈密顿路(归纳),其 «端点 » 经 «商 » 的 Følner 型 «错位 » 在 «全群 » 中闭合——陈–昆波的 «秩差 » 论证保证 «闭合步 » 不撞已用元素。退化情形(两元素生成 ℤ/m×ℤ/n 的 «细环面 »)单独处理。□

命题 2(二面体与非交换小类,完整陈述) 二面体群 D2n 的凯莱图(任意生成集)有哈密顿圈(经 «a-圈 + b-跳跃 » 的显式构造);对称群的 «星树 » 生成集有哈密顿圈(«星型 » 排列的组合构造——阿克斯诺维奇的 «排位 » 方法)。

命题 3(三条统一路线,完整陈述) ①«提升法 »:商图哈密顿 + «纤维 » 的错位闭合(交换情形的普遍化——受制于 «关系 » 的扭曲);②«因子图法 »:把凯莱图表为 «2-因子的边不交并 »(«生成元的圈分解 » ——罗瓦兹 «2-因子可分解 ⟹ 哈密顿 » 的猜想方向);③«算法法 »:哈密顿圈的 «群论搜索 »(GAP 大规模验证 + «回溯启发式 » ——小群全验证通过)。三条路线在 «Sn 一般生成集 » 处同时卡住。

进展与文献

Chen–Quimpo 1976(交换完整解);Witte(Cayley 图哈密顿性的群论综述,1990s);László Lovász 的顶点传递问题原始文献;Conder–Tihany 的 «多数顶点传递图验证 » 大规模计算。开放核心:Sn 与李型群的一般生成集情形;罗瓦兹 «路版本 » 的完全证明(它是本问题的 «超集 » ——顶点传递图不必是凯莱图);与 «随机凯莱图 » 的哈密顿性概率(«随机生成元 ⟹ 高概率哈密顿 » 已有部分结果)。

← 返回问题 24