凱萊圖

维基百科,自由的百科全书
跳转至: 导航搜索
在兩個生成元 ab 上的自由群的凱萊圖

數學中,凱萊圖也叫做凱萊著色圖是編碼離散群。它的定義是凱萊定理(以阿瑟·凱萊命名)所暗含的,并使用這個群的特定的通常有限的生成元集合。它是組合群論與幾何群論的中心工具。

定義[编辑]

假設 G \,S \,生成集。凱萊圖 \Gamma=\Gamma(G,S) \, 是如下構造的著色的有向圖

  • G \, 每個元素 g \, 指派一個頂點: \Gamma \, 的頂點集合 V(\Gamma) \, 同一於 G \,
  • S \, 的每個生成元 s \, 指派一種顏色 c_s \,
  • 對於任何 g\in G, s\in S,對應於元素 g \,gs \, 的頂點用顏色 c_s \, 的有向邊連接。因此邊集合 E(\Gamma) \, 由形如 (g, gs) \, 的有序對構成,帶著 s\in S 提供的顏色。

在幾何群論中,集合 S \, 通常被假定為有限的、“對稱的”也就是 S=S^{-1} \,,并且不包含這個群的單位元。在這種情況下,凱萊圖是正常的: 它的邊沒有方向并且不包含環路。

例子[编辑]

  • 假設 G = Z 是無限循環群而集合 S 有標準生成元 1 和它的逆元(用加法符號為 −1)構成,則它的凱萊圖是無窮鏈。
  • 類似的,如果 G = Znn循環群S 由兩個元素構成,G 的標準生成元和它的逆元,則凱萊圖是環圖 Cn
  • 群的直積的凱萊圖是對應的凱萊圖的笛卡爾積。因此帶有四個元素(±1, ±1)組成的生成集的阿貝爾群 Z2 的凱萊圖是在平面 R2 上無窮網格,而帶有類似的生成集的直積 Zn × Zm 的凱萊圖是在環面nm 有限網格。
二面體群 D4 在兩個生成元 ab 上的凱萊圖。
  • 二面體群 D4 在兩個生成元 ab 上的凱萊圖列于右側。紅色箭頭表示左乘元素 a。因此元素 b自我逆轉的,表示左乘元素 b 藍色線是無方向的。因此這個圖是混合的: 它有 8 個頂點,8 個有向邊,4 個邊。群 D4凱萊表可以從群展示得出:
 \langle a, b | a^4 = b^2 = e, a b = b a^3 \rangle
  • 在對應於集合 S = {a, b, a−1, b−1} 的兩個生成元 a, b 上的自由群的凱萊圖列出在文章開頭,這里的 e 表示單位元。沿著邊向右走表示右乘 a,而沿著變向上走表示乘以 b。因為自由群沒有關系,它的凱萊圖中沒有。這個凱萊圖是證明巴拿赫-塔斯基悖论的關鍵因素。

特征[编辑]

G 通過左乘作用在自身上(參見凱萊定理)。這個作用可以看作 G 作用在它的凱萊圖上。明顯的,一個元素 h\in G 映射一個頂點 g\in V(\Gamma) 到頂點 hg\in V(\Gamma)。凱萊圖的邊集合被這個作用所保存: 邊 (g,gs) 變換成邊 (hg,hgs)。任何群在自身上的左乘作用是簡單傳遞的,特別是凱萊圖是頂點傳遞的。這導致了凱萊圖的下列特征:

\Gamma 是群 G 的凱萊圖,當且僅當它通過圖自同構許可 G 的簡單傳遞作用(就是保存邊的集合)。

要從一個凱萊圖 \Gamma=\Gamma(G,S) 恢復群 G 和生成集 S,選擇一個頂點 v_1\in V(\Gamma) 并標記上這個群的單位元。接著對每個 \Gamma 的頂點 v 標記上變換 v_1vG 的唯一元素。產生 \Gamma 為凱萊圖的 G 的生成元的集合 S 是毗連到選擇的頂點的頂點的標記的集合。生成集合是有限(這是凱萊圖的共同假定)當且僅當這個圖是局部有限的(就是說每個頂點毗連與有限多個邊)。

基本性質[编辑]

  • 如果生成集合的成員 s 是自身的逆元,即 s=s^{-1},則它一般被表示為無向邊。
  • 凱萊圖 \Gamma(G,S) 本質上依賴於生成元的集合 S 的選擇方式。例如,如果生成集合 Sk 個元素,則凱萊圖的每個頂點都有 k 個進入和 k 個外出的有向邊。在有 r 個元素的對稱生成集合 S 的情況下,凱萊圖是 r 度的正則圖
  • 在凱萊圖中的(“閉合路徑”)指示在 S 的兩個元素之間的關系。在群的凱萊複形的更精細構造中,對應於關系的閉合路徑被用多邊形“填充”。
  • 如果 f: G'\to G滿射群同態并且 G' 的生成集合 S' 的元素的像是不同的,則它引發一個圖的覆蓋
 \bar{f}: \Gamma(G',S')\to \Gamma(G,S),\quad 這里的 S=f(S') \,
特別是,如果群 Gk 個生成元,都有不是 2 的階,并且這些生成元和它們的逆元構成集合 S,則凱萊圖 \Gamma(G,S) 由對應於在相同生成集合的自由群2k 度無限正則所覆蓋。
  • \Gamma(G,S) 可以被構造即使集合 S 不生成群 G。但是,它是連通的并不被認為是凱萊圖。在這種情況下,這個圖的每個連通部件表示一個 S 生成子群的陪集。

Schreier陪集圖[编辑]

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

與群論的關系[编辑]

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

參見[编辑]

注釋[编辑]

  1. ^ Babai, L. Technical Report TR-94-10. University of Chicago. 1996. [1]