二面体群 $D_{2p}$ 上 Cay-DS Cayley 图的完全分类

《Journal of Algebra》：A complete classification of Cay-DS Cayley graphs on the dihedral group D 2 p

　　

摘要
设 G 为一个有限群，且令 ?? ??? ?{1} 为逆封闭的。如果 G 上每一个与它共谱的凯莱图都与它同构，则称 Cay?(??,??) 为 Cay-DS。对于固定的群 G，如果 G 上每一个度为 d 的凯莱图都是 Cay-DS 的，则称度 d 为 Cay-DS 强制的。在本文中，我们完成了二面体群 ??2???（阶为 2p）的凯莱图的 Cay-DS 强制度的分类。对于已知的小素数情形 ?? ∈{2,3,5,7,11}，每一个度都是 Cay-DS 强制的。对于每一个素数 ?? ≥13，Cay-DS 强制的度恰好为 ?? ∈{0,1,…,5} ∪{2???? 6,2???? 5,…,2???? 1}。所有剩余的度 6 ≤?? ≤2???? 7 都不是 Cay-DS 强制的；这由 ??2??? 上非同构的共谱 d-正则凯莱图所证实，这些图来源于已知和新的构造。我们进一步证明中间度是混合的，意义如下：对于每一个素数 ?? ≥13 和每一个 6 ≤?? ≤2???? 7，都存在一个 Cay-DS 图 Cay?(??2???,??) 使得 |??|= ??。

引言
凯莱图构成了有限群论和图论之间的经典桥梁。它们提供了一种将群连同其区别子集编码为高度对称图的自然而然的方式，并从代数和组合的角度进行了研究；例如，参见 [7], [13]。它们也自然地出现在互连网络 [4]、整凯莱图 [3], [15], [16] 以及具有群作用的图上的其他结构问题的研究中 [14]。从谱的角度来看，凯莱图特别有用，因为它们的邻接谱可以用底层群的不可约表示来描述；参见 Babai 的工作 [6]。

设 G 为具有单位元 1 的有限群。如果 ???1= ??，则称子集 ?? ??? ?{1} 为对称的。凯莱图 Cay?(??,??) 是以 G 为顶点集、以边集???(Cay?(??,??))={{??,?}:?????1∈??} 的简单无向图。当 G 为循环群时，Cay?(??,??) 为循环图；当 G 为二面体群时，它为二面体凯莱图。

设 Γ 为一个有限简单图，令 ???(Γ) 为其邻接矩阵。???(Γ) 的特征值多重集记为 ?????(Γ)，称为 Γ 的谱。如果两个图具有相同的谱，则称它们共谱。如果每一个与 Γ 共谱的图都与 Γ 同构，则称图 Γ 由其谱确定，或称 DS。

确定哪些图是 DS 的问题可以追溯到 Günthard 和 Primas [12]。Collatz 和 Sinogowitz [8] 证明了存在非同构的共谱图，Schwenk [20] 证明了几乎所有的树都不是 DS。这些结果表明，对于一般图，谱并没有以任何简单的方式确定同构类型。DS 问题此后成为谱图论中的一个重要主题；参见综述 [9], [10]。

对于凯莱图，人们可以提出 DS 问题的一个更具群论版本。凯莱图 Cay?(??,??) 被称为 Cay-DS，如果同一群 G 上每一个与 Cay?(??,??) 共谱的凯莱图都与 Cay?(??,??) 同构。因此，Cay-DS 性质询问谱是否在该固定群上的凯莱图族内确定了凯莱图。每一个 DS 凯莱图都是 Cay-DS 的，但反之未必成立；参见 [2]。如果一个有限群 G 上每一个无向凯莱图都是 Cay-DS 的，则称 G 为 Cay-DS 群。

Cay-DS 问题对于循环群和二面体群进行了特别的研究。对于循环群，Elspas 和 Turner [11] 证明了每一个奇素数阶的循环图都是 Cay-DS 的，并展示了合成阶上的非同构共谱循环图。[17] 获得了某些素数幂和半素数阶的进一步结果。这些结果表明，Cay-DS 性质与底层群的算术和群论结构密切相关。

在本文中，我们研究二面体群??2???=〈??,??|????=??2=1,????????=???1〉={1,??,…,?????1,??,?????,…,????????1} 的 Cay-DS 问题，其中 p 为素数。在此方向上的第一个非平凡正结果是三次情形，由 Huang、Huang 和 Lu 解决。

定理 1.1 [18]
设 p 为奇素数。每一个满足 |??|= 3 的凯莱图 Cay?(??2???,??) 都是 Cay-DS 的。

对于较大的度，情况发生了根本变化。Abdollahi、Janbaz 和 Ghahramani 构造了二面体群上大量的共谱非同构凯莱图族。在此处所需的情形下，他们的结果给出如下。

定理 1.2 [1]
对于每一个素数 ?? ≥23 和每一个整数 d 满足 6 ≤?? ≤2???? 7，??2??? 上存在两个非同构的共谱 d-正则凯莱图。

??2??? 的全局 Cay-DS 群性质由 Abdollahi、Janbaz 和 Jazaeri 分类。

定理 1.3 [2]
设 p 为素数。则 ??2??? 为 Cay-DS 群当且仅当 ?? ∈{2,3,5,7,11}。

因此，对于 ?? ≥13，群 ??2??? 不是 Cay-DS 群。然而，定理 1.3 只给出了全局阻碍：它表明 ??2??? 上至少有一个凯莱图不是 Cay-DS 的，但它没有描述这种失败是如何分布在可能的价数中的。这激发了以下 Cay-DS 群问题的逐度细化。

设 0 ≤?? ≤2???? 1。如果每一个满足 |??|= ?? 的对称连接集 ?? ???2??? ?{1} 都给出一个 Cay-DS 图 Cay?(??2???,??)，则称 d 为 ??2??? 的 Cay-DS 强制度。

问题 1.4
对于素数 p，确定 ??2??? 的 Cay-DS 强制度。对于每一个剩余度，确定是否存在至少一个该度的 Cay-DS 凯莱图。

我们的第一个主要结果给出了问题 1.4 强制部分的完整答案。

定理 1.5
设 p 为素数且令 0 ≤?? ≤2???? 1。则 d 为 ??2??? 的 Cay-DS 强制度当且仅当 ?? ∈{2,3,5,7,11} 或者 ?? ≥13 且 ?? ∈{0,1,…,5} ∪{2???? 6,2???? 5,…,2???? 1}。

因此，当 ?? ≥13 时，唯一的强制度是低度 0,…,5 及其互补度。中间度不是强制的。我们的第二个主要结果表明这种失败是严格度普适的：它并不意味着所有该度的凯莱图都失败为 Cay-DS。

定理 1.6
设 ?? ≥13 为素数。对于每一个整数 d 满足 6 ≤?? ≤2???? 7，都存在一个对称连接集 ?? ???2??? ?{1} 使得 |??|= ?? 且 Cay?(??2???,??) 为 Cay-DS。

综上所述，定理 1.5 和 1.6 给出了 Cay-DS 群 ??2??? 分类的逐度细化。对于 ?? ≥13，每一个中间度都包含 ??2??? 上的 Cay-DS 和非 Cay-DS 凯莱图。因此，??2??? 上单个凯莱图的 Cay-DS 性质不能仅从它的度确定，而定理 1.5 精确识别了该性质被强制的度。

我们简要描述证明的主要思想。我们使用 ??2??? 的不可约表示，用 ??? 上的特征和来表达 Cay?(??2???,??) 的谱。这将共谱性简化为连接集的旋转部分和反射部分的明确算术条件。然后，这些条件与 ??2??? 的自同构结构以及 ??2??? 的 CI 性质相结合，以证明小度和互补度中的强制结果。对于非强制的中间度，我们通过添加旋转的逆对和取补来扩展已知的共谱构造。最后，所有中间度中的 Cay-DS 例子来源于反射的区间集及其补。

本文组织如下。第 2 节收集了凯莱谱、有限群表示、??2??? 自同构以及后续使用的 CI 性质的必要预备知识。第 3 节证明定理 1.5 和 1.6。我们首先推导 ??2??? 上凯莱图的谱分解，然后证明 Cay-DS 强制度的分类，最后构造所有中间度中的 Cay-DS 凯莱图。

章节片段
预备知识
在本节中，我们回顾一些必要的定义并呈现一些先前已知的结果，这些将用于我们主要结果的证明中。

设 G 为有限群，令 V 为复数域 ? 上的有限维向量空间。记 ??????(??) 为所有可逆线性映射 ?? :?? →?? 的群。G 在 V 上的表示是一个群同态 ?? :?? →??????(??)。ρ 的度是 V 的维数。假设 V 是一个酉空间，即它配备了 Hermitian 内积

定理 1.5 和 1.6 的证明
在本节中我们假设 ?? ≥3。情形 ??= 2 由定理 1.3 覆盖。我们首先证明定理 1.5；最后一小节证明定理 1.6。
黄晶