凱萊圖(英語:Cayley graph),也叫做凱萊著色圖,是將離散群的抽象結構畫出的一種。它的定義是凱萊定理(以阿瑟·凱萊命名)所暗含的。畫凱萊圖時,要選定群的一個生成元集合(通常有限),不同選法可能得到不同的凱萊圖。凱萊圖是組合群論英語Combinatorial group theory幾何群論英語Geometric group theory的中心工具。

在兩個生成元ab上的自由群的凱萊圖

定義

假設 ,而 G的生成集。凱萊圖 ,是如下構造的著色的有向圖

  •  的每個元素 對應一個頂點。換言之,圖 的頂點集合 視為與 等同;
  •  中每個生成元 ,對應一種顏色 
  • 對於任何 ,畫一條由元素  有向邊,染成 色。換言之,邊集合 由形如 的有序對構成,邊的顏色由 確定。

在幾何群論中,集合 通常取為有限、對稱(即滿足 ),並且不包含這個群的單位元 。在這種情況下,凱萊圖是簡單無向圖:它的邊沒有方向(由對稱性),並且不包含自環(因為 )。

例子

  • 假設 是無限循環群(即整數的加法群),而集合 由標準生成元 和它的逆元(用加法符號為 )構成,則它的凱萊圖是無窮鏈英語Path graph
  • 類似地,如果  循環群(模 的加法群),而 仍由 的標準生成元 與逆元 構成,則凱萊圖是環圖 
  • 群的直積的凱萊圖(新生成集取為原生成集之笛卡爾積),是對應的凱萊圖的笛卡爾積英語Cartesian product of graphs。因此阿貝爾群 ,關於四個元素 組成的生成集的凱萊圖,是平面 上的無窮網格,而帶有類似的生成集的直積 的凱萊圖,是環面上的  有限網格。
  • 二面體群 群展示 左圖是關於兩個生成元  的凱萊圖,其中紅色箭頭表示左乘元素 (順時針旋轉 )。而因為元素 (左右反射)自反,所以表示左乘元素 的藍色線是無方向的,故左圖混合了有向邊與無向邊:它有 個頂點、 有向邊 條無向邊。
     
    二面體群 關於兩個生成元  的凱萊圖。
     
     關於兩個自反生成元的凱萊圖
    同一個群 ,亦可畫出不同的凱萊圖,如右圖。 仍表示左右反射,而 則是關於主對角線的反射,以粉紅色線表示。由於兩個反射皆自反,右邊的凱萊圖完全無向。對應的群展示是 
  • 條目開頭的圖,是兩個生成元 上的自由群,關於生成集合 的凱萊圖,而正中央的黑點,是單位元 。沿著邊向右走表示右乘 ,而沿著邊向上走表示乘以 。因為自由群沒有關係,它的凱萊圖中沒有。這個凱萊圖是證明巴拿赫-塔斯基悖論的關鍵。
  • 右邊有離散海森堡群
     
    海森堡群的一部分(顏色僅為方便看清分層)

  的凱萊圖。所用的三個生成元 ,分別對應 。其關係為 ,亦可從圖中看出。本群為非交換無窮群。雖然是三維空間,其凱萊圖的增長英語Growth rate (group theory)卻是 階的。[來源請求]

特徵

 通過左乘作用在自身上(參見凱萊定理)。這個作用可以看作 作用在它的凱萊圖上。明確而言,一個元素 映射一個頂點 到另一個頂點 。凱萊圖的邊集合被這個作用所保存:邊 變換成邊 。任何群在自身上的左乘作用是簡單傳遞的,特別是凱萊圖是頂點傳遞英語Vertex-transitive graph的。事實上,反向的結論也成立,即有下列等價刻劃,稱為扎比杜西定理(英語:Sabidussi's Theorem):

(無標記又無着色)有向圖 是群 的某個凱萊圖,當且僅當 可作為圖自同構(就是要保存邊的集合)作用在 上,且該作用簡單傳遞。[1]

要從一個凱萊圖 找回群 和生成集 ,先選擇一個頂點 ,標上群的單位元 。接著,對 的每個頂點  中有唯一元素將 變換到 ,於是可以在 處標記該唯一元素。最後要確定 的哪個生成集 ,產生凱萊圖 ,而所求的 就是毗連 的頂點標記的集合。生成集合是有限(這是凱萊圖的共同假定)當且僅當這個圖是局部有限的(就是說每個頂點僅毗連於有限多條邊)。

基本性質

  • 如果生成集合的成員 是自身的逆元,即 ,則它一般被表示為無向邊
  • 凱萊圖 本質上依賴於如何選擇生成集 。例如,如果生成集合  個元素,則凱萊圖的每個頂點都有 有向邊進入, 條有向邊外出。當生成集合 為對稱集,且有 個元素時,凱萊圖是 度的正則圖
  • 在凱萊圖中的(「閉合路徑」)指示 的元素之間的關係。在群的凱萊複形此一更複雜的構造中,對應於關係的閉合路徑被用多邊形「填充」。
  • 如果 滿射群同態並且 的生成集合 的元素的像是不同的,則導出圖覆疊英語Covering graph映射 這里的 ,特別是,如果群  個生成元,階均不為 ,並且這些生成元和它們的逆元構成集合 ,則該集合生成的自由群 有到 的滿同態(商映射),故 被自由群的凱萊圖覆蓋,即 度的無限正則
  • 即使集合 不生成群 ,仍可以構造圖 。但是,此情況下,所得的圖並不連通。在這種情況下,這個圖的每個連通分支對應 所生成子群的一個陪集。
  • 對於有限凱萊圖(視為無向),其頂點連通性等於這個圖的 。若生成集極小(即移除任一元素及其逆元,就不再生成整個群),則其頂點連通性等於度數。[2]至於邊連通性,則在任何情況下皆等於度數。[3]
  •  的每個乘性特徵標英語Multiplicative character 都給出 鄰接矩陣特徵向量。若 為交換群,則對應的特徵值 特別地,平凡特徵標(將所有元素映至常數 )對應的特徵值,等於 的度數,即 的元素個數。若 為交換群,則恰有 個特徵標,故已足以確定全部特徵值。

Schreier陪集圖

如果轉而把頂點作為固定子群 的右陪集,就得到了一個有關的構造Schreier陪集圖,它是陪集枚舉Todd-Coxeter算法的基礎。

與群論的關係

研究圖的鄰接矩陣特別是應用譜圖理論的定理能洞察群的結構。

參見

注釋

  1. ^ Sabidussi, Gert. On a class of fixed-point-free graphs [論一類無不動點的圖]. Proceedings of the American Mathematical Society. October 1958, 9 (5): 800–4. JSTOR 2033090. doi:10.1090/s0002-9939-1958-0097068-7  (英語). 
  2. ^ Babai, L. Technical Report TR-94-10. University of Chicago. 1996. 存档副本. [2010-08-29]. (原始內容存檔於2010-06-11). 
  3. ^ 見定理3.7,Babai, László. 27. Automorphism groups, isomorphism, reconstruction [第27章:自同構群、同構、重構] (PDF). Graham, Ronald L.; Grötschel, Martin; Lovász, László (編). Handbook of Combinatorics [組合手冊] 1. Elsevier. 1995: 1447–1540 [2021-09-29]. ISBN 9780444823465. (原始內容存檔於2021-04-22).