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

阿达姆猜想(CI 图)

《图论中的 50 个公开问题》 · 问题 41 专题综述

题面两个凯莱图同构何时能由生成元的群自同构解释(CI 性质)?

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

问题

群 G、生成集 S:Cay(G,S) 具有 CI 性质(cyclic-isomorphism),若对每个 «同构的凯莱图» Cay(G,T),存在群自同构 α ∈ Aut(G) 使 α(S) = T。阿达姆 1967 猜想:循环群的一切 «k 元 » 生成集有 CI 性质——被 🅚?» 反例(Ádám 本人 1969 就给出小反例; Širáň 等的 «双反例 » 族)修正为: «哪些群、哪些生成集有 CI?»

主要概念

CI 的算法意义

CI 性质把 «凯莱图同构 »(一般图同构的特例)归约为 «生成集在 Aut(G) 下的轨道判定 »—— «群论算法 » 可解。故 CI 是 «凯莱图系统枚举 »( «有多少非同构凯莱图 »)的钥匙:CI 群上 «同构 ⟺ 生成集同轨 »,枚举 = «轨道枚举 »。

反例的机制

Ádám 反例的核心: «乘法 » 自同构( «标量 »)不够, «仿射 » 之外的 «普通 » 图同构存在—— «循环群 » 上 « Cay(ℤₙ, ±{a}) 型 » «意外同构 »: «两套生成集 » 的图同构但 «不存在 » 把一套送到另一套的 «乘 » 运算—— «仿射 » 自同构 «含平移 » 的 «微妙 » 边界。

主要命题与证明

命题 1(Alspach 定理,完整陈述) ℤp(p 素)上:两个 «k 元 » 生成集的凯莱图同构 ⟺ 存在 α ∈ Aut(ℤp)( «标量乘 »)与平移使 S 送到 T—— «p 素 ⟹ CI 完整 »。

梗概  «平凡 » 自同构块( «平移 »)吸收 «顶点 » 自由; «稳定一点 » 的同构属于 «乘法 » 仿射; «p 素 » 的 «循环群 » 的 «凯莱 » 结构 «仿射 » 完备( «凯莱 » 的 «点稳定 » 同构群 ⊆ 仿射—— «Burnside 型 » 论证)。□

命题 2(CI 的传递性质) 若 G 有 «k-CI»( «k 元生成集 »)与 «m-CI», «结构合适 » 时 G 有 «(k+m−1)-CI»—— «CI 的 «加 » 引理 »;由此 «素幂 » 群、 «循环 » 群的大量 «k 层 » CI 被逐级建立。

进展与文献

Ádám 1967 原猜想与 1969 反例;Alspach 1984+( «Pm 群 CI» 系);Li C. H. 的 «CI-图 » 综述( «有限群 » 的 «CI 图 » 全景);Dobson–Morris 的 «CI 与枚举 » 算法线;Širáň–Škoviera 的反例族。开放核心: «完整分类 »:哪些群 «全 CI»( «所有生成集 »)—— «素幂 » 已知、 «2·奇 » 半开; «一般凯莱同构 » 的 «群论 » 判定算法(与 37 号 GI、26/27 号哈密顿同属凯莱四大前沿)。

← 返回问题 41