Graph defined from a mathematical group
2つの生成元a と b 上の 自由群 のケーリーグラフ 数学 において 、 ケイリーグラフ（ケイリーグラフ、 ケイリーカラーグラフ 、 ケイリー図 、 群図 、 カラーグループ とも呼ばれる ） [1]は、 群 の抽象的な構造を符号化した グラフ である。その定義は ケイリーの定理（ アーサー・ケイリー にちなんで名付けられた） によって示唆され 、群に対して特定の 生成元集合を用いる。これは、 組合せ論的 および 幾何学的群論 における中心的なツールである。ケイリーグラフの構造と対称性は、 エクスパンダーグラフ の構築に特に適している 。
意味 を群 とし 、 を 生成集合 と する 。ケイリーグラフは、 以下のように構成される 辺色 有向グラフ である。 [2] G {\displaystyle G} S {\displaystyle S} G {\displaystyle G} Γ = Γ ( G , S ) {\displaystyle \Gamma =\Gamma (G,S)}
の 各要素に は頂点が割り当てられている。頂点集合は 次のように表される。 g {\displaystyle g} G {\displaystyle G} Γ {\displaystyle \Gamma } G . {\displaystyle G.} の 各要素に は色が割り当てられます 。 s {\displaystyle s} S {\displaystyle S} c s {\displaystyle c_{s}} および ごとに 、 に対応する頂点 から に対応する頂点への 色の有向辺が存在します 。 g ∈ G {\displaystyle g\in G} s ∈ S {\displaystyle s\in S} c s {\displaystyle c_{s}} g {\displaystyle g} g s {\displaystyle gs} すべての慣例において、 が 群を生成することを要求するわけではありません。 が の生成集合でない場合 、は 非連結 であり 、各連結成分は によって生成される部分群の剰余類を表します 。 S {\displaystyle S} S {\displaystyle S} G {\displaystyle G} Γ {\displaystyle \Gamma } S {\displaystyle S}
の 要素が それ自身の逆である場合、 それは通常、無向エッジによって表されます。 s {\displaystyle s} S {\displaystyle S} s = s − 1 , {\displaystyle s=s^{-1},}
集合は 有限であると仮定されることが多く、特に 幾何学的群論 では有限であることが想定され、これは局所有限であることと有限生成であること に対応します 。 S {\displaystyle S} Γ {\displaystyle \Gamma } G {\displaystyle G}
集合は 対称 （ ） であり 、群 単位元 を含まないと仮定されることがある。この場合、無彩色ケーリーグラフは単純な無向 グラフ として表すことができる。 S {\displaystyle S} S = S − 1 {\displaystyle S=S^{-1}}
例 が 無限巡回群であり、その集合が 標準生成元 1 とその逆元 (加法表記では -1) から構成されるとすると、ケイリー グラフは無限パスになります。 G = Z {\displaystyle G=\mathbb {Z} } S {\displaystyle S} 同様に、 が位数の 有限 巡回群 であり、集合が の標準生成元 とその逆元という2つの要素から成る場合、ケイリーグラフは 巡回 グラフ となる。より一般的には、有限巡回群のケイリーグラフはまさに 巡回グラフ となる。 G = Z n {\displaystyle G=\mathbb {Z} _{n}} n {\displaystyle n} S {\displaystyle S} G {\displaystyle G} C n {\displaystyle C_{n}} 群の直積 （生成集合の 直積 を生成集合とする） のケイリーグラフは 、対応するケイリーグラフの 直積である。 [3] したがって、 4つの元からなる生成子の集合を持つ アーベル群のケイリーグラフは 平面上の 無限 グリッド であるが、同様の生成子を持つ 直積の場合、ケイリーグラフは トーラス 上の有限グリッドである 。 Z 2 {\displaystyle \mathbb {Z} ^{2}} ( ± 1 , 0 ) , ( 0 , ± 1 ) {\displaystyle (\pm 1,0),(0,\pm 1)} R 2 {\displaystyle \mathbb {R} ^{2}} Z n × Z m {\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{m}} n × m {\displaystyle n\times m} 2つの生成元a と b 上の二面体 群のケーリーグラフ D 4 {\displaystyle D_{4}} のケーリーグラフ 、2つの生成元は両方とも自己逆である D 4 {\displaystyle D_{4}} 2つの生成元と 上の二面体 群 のケイリーグラフを 左側に示します。赤い矢印は との合成を表します 。は 自己逆 なので 、 との合成を表す青い線は 無向です。したがって、グラフは混合グラフです。つまり、8つの頂点、8つの矢印、4つの辺を持ちます。 の ケイリー表は、 グループのプレゼンテーション から導くことができます。 の別のケイリーグラフを 右側に示します。 は依然として水平反射であり、青い線で表され、 は 対角反射であり、ピンクの線で表されます。両方の反射が自己逆なので、右側のケイリーグラフは完全に無向です。このグラフは、プレゼンテーションに対応します。 D 4 {\displaystyle D_{4}} a {\displaystyle a} b {\displaystyle b} a {\displaystyle a} b {\displaystyle b} b {\displaystyle b} D 4 {\displaystyle D_{4}} ⟨ a , b ∣ a 4 = b 2 = e , a b = b a 3 ⟩ . {\displaystyle \langle a,b\mid a^{4}=b^{2}=e,ab=ba^{3}\rangle .} D 4 {\displaystyle D_{4}} b {\displaystyle b} c {\displaystyle c} ⟨ b , c ∣ b 2 = c 2 = e , b c b c = c b c b ⟩ . {\displaystyle \langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle .} 集合 に対応する 2つの生成元 と上の 自由群 のケイリーグラフは 、本記事の冒頭に示されています。 は 恒等関数です。右への辺の移動は による右乗算を表し、 上への辺の移動は による乗算に対応します。 自由群には の 関係がないため、ケイリーグラフには 閉路 がありません。つまり、ケイリーグラフ は4元 正則 無限 木です。これは バナッハ＝タルスキーのパラドックス の証明における重要な要素です 。 a {\displaystyle a} b {\displaystyle b} S = { a , b , a − 1 , b − 1 } {\displaystyle S=\{a,b,a^{-1},b^{-1}\}} e {\displaystyle e} a , {\displaystyle a,} b . {\displaystyle b.} より一般的には、 ベーテ格子 またはケイリー木は、生成元上の自由群のケイリーグラフである 。 生成元 による 群の 表現 は、生成元上の自由群から、 ケイリー木から のケイリーグラフへの写像を定義する 群への射影 準同型 に対応する。グラフを 1次元 単体複体として 位相的 に解釈すると、 単連結 無限木はケイリーグラフの 普遍被覆 であり、 写像の 核はケイリーグラフの 基本群 である。 n {\displaystyle n} G {\displaystyle G} n {\displaystyle n} n {\displaystyle n} G , {\displaystyle G,} G {\displaystyle G} ハイゼンベルク群のケーリーグラフの一部。（色分けは視覚的な補助のみを目的としています。） 離散ハイゼンベルク群 のケーリーグラフ を右に描いている。図中で用いられている生成元は、 要素 に対する 1, 0, 0 の3つの順列によって与えられる3つの行列である 。これらは の関係を満たしており 、これは図からも理解できる。これは 非可換 無限群であり、3次元空間に埋め込まれているにもかかわらず、ケーリーグラフは4次元の 体積成長 を持つ。 [4] { ( 1 x z 0 1 y 0 0 1 ) , x , y , z ∈ Z } {\displaystyle \left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}} X , Y , Z {\displaystyle X,Y,Z} x , y , z {\displaystyle x,y,z} Z = X Y X − 1 Y − 1 , X Z = Z X , Y Z = Z Y {\displaystyle Z=XYX^{-1}Y^{-1},XZ=ZX,YZ=ZY} 四元数 i 、 j 、 k による乗算の循環を示すケーリー Q8 グラフ
キャラクター設定 群は 左乗法によって自身に 作用する（ ケーリーの定理 を 参照）。これは のケーリーグラフへの作用と見ることができる 。明示的には、元は 頂点を 頂点 に写像する 。ケーリーグラフの辺の集合とその色はこの作用によって保存される。すなわち、辺 は 辺 に写像され 、両方とも色 を持つ 。実際、 色付き有向グラフ のすべての 自己同型は この形式であるため、 は の 対称群 と同型である 。 [注 1] [注 2] G {\displaystyle G} G {\displaystyle G} h ∈ G {\displaystyle h\in G} g ∈ V ( Γ ) {\displaystyle g\in V(\Gamma )} h g ∈ V ( Γ ) . {\displaystyle hg\in V(\Gamma ).} ( g , g s ) {\displaystyle (g,gs)} ( h g , h g s ) {\displaystyle (hg,hgs)} c s {\displaystyle c_{s}} Γ {\displaystyle \Gamma } G {\displaystyle G} Γ {\displaystyle \Gamma }
群の自身への左乗法作用は 単純に推移的 であり、特にケーリーグラフは 頂点推移的 である。以下はこれの逆である。
ラベルなし有向グラフ から 群 と生成集合を復元するには 、頂点を1つ選び 、群の単位元でラベル付けします。次に、 の各頂点 を に 写像する の一意の元でラベル付けします。 の 生成元 集合は となります。 ケーリーグラフは の外近傍 のラベル集合です 。 は無彩色であるため、 の左乗法写像よりも多くの有向グラフ自己同型を持つ可能性があります。例えば、 の群自己同型は を置換します 。 G {\displaystyle G} S {\displaystyle S} Γ {\displaystyle \Gamma } v 1 ∈ V ( Γ ) {\displaystyle v_{1}\in V(\Gamma )} v {\displaystyle v} Γ {\displaystyle \Gamma } G {\displaystyle G} v 1 {\displaystyle v_{1}} v . {\displaystyle v.} S {\displaystyle S} G {\displaystyle G} Γ {\displaystyle \Gamma } Γ ( G , S ) {\displaystyle \Gamma (G,S)} v 1 {\displaystyle v_{1}} Γ {\displaystyle \Gamma } G {\displaystyle G} S {\displaystyle S}
基本的な性質 ケイリーグラフは、生成元 集合の選択に本質的に依存する 。例えば、生成元集合に元が ある場合 、ケイリーグラフの各頂点には 入ってくる有向辺と出て いく 有向辺が存在する。対称な生成元集合の場合 、ケイリーグラフは 次数1の 正則な有向グラフとなる。 Γ ( G , S ) {\displaystyle \Gamma (G,S)} S {\displaystyle S} S {\displaystyle S} k {\displaystyle k} k {\displaystyle k} k {\displaystyle k} S {\displaystyle S} r {\displaystyle r} r . {\displaystyle r.} ケイリーグラフにおける 閉路 （または 閉路 ）は、 の要素間の 関係 を示す。群の ケイリー複体 のより精巧な構築においては、関係に対応する閉路は 多角形 によって「埋められる」 。これは、与えられた表現のケイリーグラフを構築する問題は、 の 文章問題 を 解くことと等価であることを意味する 。 [1] S . {\displaystyle S.} P {\displaystyle {\mathcal {P}}} P {\displaystyle {\mathcal {P}}} が 射影 群準同型 で、 の生成 集合 の元の像が 異なる場合、 のグラフの被覆が誘導されます。 特に 、グループにすべての次数が 2 と異なる生成元 があり 、集合が これらの生成元とその逆生成元で構成される場合、ケイリー グラフは同じ生成元集合上の 自由群 に対応する 次数の無限正規 木 によって覆われます 。 f : G ′ → G {\displaystyle f:G'\to G} S ′ {\displaystyle S'} G ′ {\displaystyle G'} f ¯ : Γ ( G ′ , S ′ ) → Γ ( G , S ) , {\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),} S = f ( S ′ ) . {\displaystyle S=f(S').} G {\displaystyle G} k {\displaystyle k} S {\displaystyle S} Γ ( G , S ) {\displaystyle \Gamma (G,S)} 2 k {\displaystyle 2k} 無向グラフとみなされる有限ケイリーグラフにおいて、 頂点の連結性はグラフの 次数 の2/3以上である 。生成集合が最小の場合（生成集合から任意の要素と、もし存在するならばその逆元を除去すると、生成集合ではなくなる）、頂点の連結性は次数に等しい。 辺の連結性 は、すべての場合において次数に等しい。 [6] が で表された行列形式 を持つ左正規表現である 場合 、 の隣接行列は です 。 ρ reg ( g ) ( x ) = g x {\displaystyle \rho _{\text{reg}}(g)(x)=gx} | G | × | G | {\displaystyle |G|\times |G|} [ ρ reg ( g ) ] {\displaystyle [\rho _{\text{reg}}(g)]} Γ ( G , S ) {\displaystyle \Gamma (G,S)} A = ∑ s ∈ S [ ρ reg ( s ) ] {\textstyle A=\sum _{s\in S}[\rho _{\text{reg}}(s)]} 群の すべての群 指標は 、の 隣接行列 の 固有ベクトルを 誘導します 。関連付けられた 固有値 は で 、 がアーベル群のとき、 整数 に対して の 形を取ります。 特に、自明な指標（すべての要素を 1 にする指標）の関連付けられた固有値は の次数 、つまり の位数です 。 が アーベル群 の場合 、すべての固有値を決定する指標はちょうど 個あります 。対応する固有ベクトルの直交基底は で与えられます。 この固有基底は生成集合 に依存しないことは興味深いことです 。 χ {\displaystyle \chi } G {\displaystyle G} Γ ( G , S ) {\displaystyle \Gamma (G,S)} λ χ = ∑ s ∈ S χ ( s ) , {\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi (s),} G {\displaystyle G} ∑ s ∈ S e 2 π i j s / | G | {\displaystyle \sum _{s\in S}e^{2\pi ijs/|G|}} j = 0 , 1 , … , | G | − 1. {\displaystyle j=0,1,\dots ,|G|-1.} Γ ( G , S ) {\displaystyle \Gamma (G,S)} S {\displaystyle S} G {\displaystyle G} | G | {\displaystyle |G|} v j = 1 | G | ( 1 e 2 π i j / | G | e 2 ⋅ 2 π i j / | G | e 3 ⋅ 2 π i j / | G | ⋯ e ( | G | − 1 ) 2 π i j / | G | ) . {\displaystyle v_{j}={\tfrac {1}{\sqrt {|G|}}}{\begin{pmatrix}1&e^{2\pi ij/|G|}&e^{2\cdot 2\pi ij/|G|}&e^{3\cdot 2\pi ij/|G|}&\cdots &e^{(|G|-1)2\pi ij/|G|}\end{pmatrix}}.} S {\displaystyle S}
より一般的には、対称生成集合について、 の既約表現の完全集合をとり 、 を 固有値集合 とします 。すると、 の固有値集合は、 が の固有値として 現れるたびに、が 重複して現れる ところと 全く同じになります。 ρ 1 , … , ρ k {\displaystyle \rho _{1},\dots ,\rho _{k}} G , {\displaystyle G,} ρ i ( S ) = ∑ s ∈ S ρ i ( s ) {\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)} Λ i ( S ) {\displaystyle \Lambda _{i}(S)} Γ ( G , S ) {\displaystyle \Gamma (G,S)} ⋃ i Λ i ( S ) , {\textstyle \bigcup _{i}\Lambda _{i}(S),} λ {\displaystyle \lambda } dim ( ρ i ) {\displaystyle \dim(\rho _{i})} λ {\displaystyle \lambda } ρ i ( S ) . {\displaystyle \rho _{i}(S).}
シュライア剰余類グラフ 代わりに、頂点を固定された部分群の右剰余類とすると 、関連する構成である シュライア剰余類グラフが得られます。これは、 剰余類列挙 または トッド・コクセター過程 の基礎となります 。 H , {\displaystyle H,}
群論との関連 群の構造に関する知識は、 グラフの 隣接行列を研究し、特に スペクトルグラフ理論 の定理を適用することで得られる。逆に、対称生成集合の場合、スペクトル理論と表現理論は 直接結びついている。すなわち 、 の既約表現の完全な集合を取り 、 を固有値 とする 。すると、 の固有値の集合は、 が の固有値として 出現するたびに 、 が重複して現れる まさにその 位置になる。 Γ ( G , S ) {\displaystyle \Gamma (G,S)} ρ 1 , … , ρ k {\displaystyle \rho _{1},\dots ,\rho _{k}} G , {\displaystyle G,} ρ i ( S ) = ∑ s ∈ S ρ i ( s ) {\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)} Λ i ( S ) {\displaystyle \Lambda _{i}(S)} Γ ( G , S ) {\displaystyle \Gamma (G,S)} ⋃ i Λ i ( S ) , {\textstyle \bigcup _{i}\Lambda _{i}(S),} λ {\displaystyle \lambda } dim ( ρ i ) {\displaystyle \dim(\rho _{i})} λ {\displaystyle \lambda } ρ i ( S ) . {\displaystyle \rho _{i}(S).}
群の種数とは、その群の任意のケーリーグラフの最小の種数である。 [ 7 ]
幾何群論 無限群の場合、 ケーリーグラフの 粗幾何学は 幾何学群論 の基礎となる。 有限生成群 の場合、これは生成元の有限集合の選択とは独立であり、したがって群の固有の性質となる。これは無限群の場合にのみ興味深い。なぜなら、群全体を生成元の有限集合として選択できるため、すべての有限群は点（または自明群）と粗同値であるからである。
正式には、与えられた生成元に対して、 計量 （ケーリーグラフ上の自然距離）という言葉があり、これによって 計量空間 が決定される。この空間の粗 同値類 は群の不変量である。
拡張プロパティ のとき 、ケイリーグラフは-正則 なので、スペクトル法を用いて グラフの 展開特性 を解析することができます。特にアーベル群の場合、ケイリーグラフの固有値はより容易に計算でき、 で与えられ、 上側の固有値は に等しいため、 チーガーの不等式 を用いてスペクトルギャップを用いて辺展開比を制限できます 。 S = S − 1 {\displaystyle S=S^{-1}} Γ ( G , S ) {\displaystyle \Gamma (G,S)} | S | {\displaystyle |S|} λ χ = ∑ s ∈ S χ ( s ) {\textstyle \lambda _{\chi }=\sum _{s\in S}\chi (s)} | S | {\displaystyle |S|}
表現論は、カズダン性（T） の形で、このような拡張ケイリーグラフを構築するために用いることができる 。以下の命題が成り立つ： [8]
離散群が カジュダンの性質 (T) を持ち、 の 有限で対称な生成集合である場合、 の像に関するの ケーリーグラフ の 任意の有限商に対して が -展開子となるような、 のみ に依存する 定数が存在する 。 G {\displaystyle G} S {\displaystyle S} G {\displaystyle G} c > 0 {\displaystyle c>0} G , S {\displaystyle G,S} Q {\displaystyle Q} G {\displaystyle G} Q {\displaystyle Q} S {\displaystyle S} c {\displaystyle c} たとえば、グループは特性 (T) を持ち、 基本行列 によって生成され 、これにより拡張グラフの比較的明示的な例が得られます。 G = S L 3 ( Z ) {\displaystyle G=\mathrm {SL} _{3}(\mathbb {Z} )}
積分分類 積分グラフとは、固有値がすべて整数であるグラフのことです。積分グラフの完全な分類は未解決の問題ですが、特定の群のケイリーグラフは常に積分です。ケイリーグラフのスペクトルに関するこれまでの特徴づけを用いると、 が 積分であるためには、 の固有値が の任意の 表現に対して積分となることが 必須です 。 Γ ( G , S ) {\displaystyle \Gamma (G,S)} ρ ( S ) {\displaystyle \rho (S)} ρ {\displaystyle \rho } G {\displaystyle G}
ケーリー積分単純群 群が ケイリー積分単純 (CIS) であるとは、 対称生成集合が の部分群の補集合であるときに、連結ケイリーグラフが整式となることである 。Ahmady、Bell、Mohar の結果は、すべての CIS 群が 、または 素数に対して と同型であることを示している 。 [9] ケイリーグラフが連結であるためには、が 実際に群全体を生成する ことが重要である。( が を生成しない場合でも ケイリーグラフは整式となる可能性があるが、 の補集合は 必ずしも部分群ではない。) G {\displaystyle G} Γ ( G , S ) {\displaystyle \Gamma (G,S)} S {\displaystyle S} G {\displaystyle G} Z / p Z , Z / p 2 Z {\displaystyle \mathbb {Z} /p\mathbb {Z} ,\mathbb {Z} /p^{2}\mathbb {Z} } Z 2 × Z 2 {\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{2}} p {\displaystyle p} S {\displaystyle S} G {\displaystyle G} S {\displaystyle S} G {\displaystyle G} S {\displaystyle S}
の例では 、対称生成集合（グラフ同型性を除く）は G = Z / 5 Z {\displaystyle G=\mathbb {Z} /5\mathbb {Z} }
S = { 1 , 4 } {\displaystyle S=\{1,4\}} :は 固有値を持つ閉路で ある Γ ( G , S ) {\displaystyle \Gamma (G,S)} 5 {\displaystyle 5} 2 , 5 − 1 2 , 5 − 1 2 , − 5 − 1 2 , − 5 − 1 2 {\displaystyle 2,{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}}} S = { 1 , 2 , 3 , 4 } {\displaystyle S=\{1,2,3,4\}} : 固有値を 持つ Γ ( G , S ) {\displaystyle \Gamma (G,S)} K 5 {\displaystyle K_{5}} 4 , − 1 , − 1 , − 1 , − 1 {\displaystyle 4,-1,-1,-1,-1} の部分群は 整群と自明群のみであり、 整グラフを生成する対称生成集合は自明群の補集合のみである。したがって、は CIS群でなければならない。 Z / 5 Z {\displaystyle \mathbb {Z} /5\mathbb {Z} } S {\displaystyle S} Z / 5 Z {\displaystyle \mathbb {Z} /5\mathbb {Z} }
完全なCIS分類の証明は、CIS群のすべての部分群と準同型像もCIS群であるという事実を利用している。 [9]
ケーリー積分群 少し異なる概念として、ケーリー積分群があります。ケーリー積分 群では、すべての対称部分集合が 積分グラフを生成します 。 が 群全体を生成しなくてもよいことに注意してください。 G {\displaystyle G} S {\displaystyle S} Γ ( G , S ) {\displaystyle \Gamma (G,S)} S {\displaystyle S}
ケーリー整群の完全なリストは 、および の位数を持つ二巡回群で与えられ 、ここで および は 四元数群である。 [9] 証明はケーリー整群の2つの重要な性質に依存している。 Z 2 n × Z 3 m , Z 2 n × Z 4 n , Q 8 × Z 2 n , S 3 {\displaystyle \mathbb {Z} _{2}^{n}\times \mathbb {Z} _{3}^{m},\mathbb {Z} _{2}^{n}\times \mathbb {Z} _{4}^{n},Q_{8}\times \mathbb {Z} _{2}^{n},S_{3}} 12 {\displaystyle 12} m , n ∈ Z ≥ 0 {\displaystyle m,n\in \mathbb {Z} _{\geq 0}} Q 8 {\displaystyle Q_{8}}
ケーリー整群の部分群と準同型像もケーリー整群である。 群がケイリー積分であるためには、その群のすべての連結されたケイリーグラフも積分でなければならない。
正規分布とオイラー分布の生成集合 一般群 が与えられたとき 、部分集合 が の元による 共役 で閉じている 場合 （正規部分群の概念を一般化）、部分集合 は正規であり、 任意の に対して 、巡回群を生成する元の集合が にも含まれる場合、オイラーである 。Guo、Lytkina、Mazurov、および Revin による 2019 年の成果では、純粋に表現論的な手法を使用して、ケイリーグラフが 任意のオイラー正規部分集合 に対して整数であることが証明されている 。 [10] G {\displaystyle G} S ⊆ G {\displaystyle S\subseteq G} S {\displaystyle S} G {\displaystyle G} S {\displaystyle S} s ∈ S {\displaystyle s\in S} ⟨ s ⟩ {\displaystyle \langle s\rangle } S {\displaystyle S} Γ ( G , S ) {\displaystyle \Gamma (G,S)} S ⊆ G {\displaystyle S\subseteq G}
この結果の証明は比較的短い。 オイラー正規部分集合が与えられたとき、 共役 類の和集合 となるような非共役対を選択する 。次に、ケーリーグラフのスペクトルの特徴付けを用いて、 の固有値が の 既約指標を取った によって与えられることを示すことができる 。この集合の各固有値は、 原始 単位根 の の元でなければならない（ただし は 各 の 位数で割り切れなければならない）。固有値は代数的整数であるため、それらが整数であることを示すには、それらが有理数であり、 の任意 の 自己同型の下で が固定されていること を示すだけで十分である。 すべての に対して となるよう な 、 と互いに素な 何かが 存在しなければならない。また、 はオイラー正規であり、 いくつかの に対してとなるためである。 共役類を全単射 で送ると、 と は 同じサイズになり、 の 和の項を単に入れ替えるだけである 。したがって のすべての自己同型に対して が固定されているため 、は 有理数であり、したがって整数である。 S {\displaystyle S} x 1 , … , x t ∈ G {\displaystyle x_{1},\dots ,x_{t}\in G} S {\displaystyle S} Cl ( x i ) {\displaystyle \operatorname {Cl} (x_{i})} Γ ( G , S ) {\displaystyle \Gamma (G,S)} { λ χ = ∑ i = 1 t χ ( x i ) | Cl ( x i ) | χ ( 1 ) } {\textstyle \left\{\lambda _{\chi }=\sum _{i=1}^{t}{\frac {\chi (x_{i})\left|\operatorname {Cl} (x_{i})\right|}{\chi (1)}}\right\}} χ {\displaystyle \chi } G {\displaystyle G} λ χ {\displaystyle \lambda _{\chi }} Q ( ζ ) {\displaystyle \mathbb {Q} (\zeta )} ζ {\displaystyle \zeta } m t h {\displaystyle m^{th}} m {\displaystyle m} x i {\displaystyle x_{i}} λ χ {\displaystyle \lambda _{\chi }} σ {\displaystyle \sigma } Q ( ζ ) {\displaystyle \mathbb {Q} (\zeta )} k {\displaystyle k} m {\displaystyle m} σ ( χ ( x i ) ) = χ ( x i k ) {\displaystyle \sigma (\chi (x_{i}))=\chi (x_{i}^{k})} i {\displaystyle i} S {\displaystyle S} σ ( χ ( x i ) ) = χ ( x j ) {\displaystyle \sigma (\chi (x_{i}))=\chi (x_{j})} j {\displaystyle j} x ↦ x k {\displaystyle x\mapsto x^{k}} Cl ( x i ) {\displaystyle \operatorname {Cl} (x_{i})} Cl ( x j ) {\displaystyle \operatorname {Cl} (x_{j})} σ {\displaystyle \sigma } λ χ {\displaystyle \lambda _{\chi }} λ χ {\displaystyle \lambda _{\chi }} Q ( ζ ) {\displaystyle \mathbb {Q} (\zeta )} λ χ {\displaystyle \lambda _{\chi }}
したがって、 が交代群であり、 が によって与えられる順列の集合である場合 、ケイリーグラフは 整式である。 （これは、Kourovkaノートブックの以前の未解決問題を解決した。）さらに、 が対称群であり、 が すべての転置の集合または特定の元を含む転置の集合である場合、ケイリーグラフ も整式である。 G = A n {\displaystyle G=A_{n}} S {\displaystyle S} { ( 12 i ) ± 1 } {\displaystyle \{(12i)^{\pm 1}\}} Γ ( A n , S ) {\displaystyle \Gamma (A_{n},S)} G = S n {\displaystyle G=S_{n}} S {\displaystyle S} Γ ( G , S ) {\displaystyle \Gamma (G,S)}
歴史 ケイリーグラフは、 1878年に アーサー・ケイリー によって有限群に対して初めて考察された。 [2] マックス・デーンは、 1909年から1910年にかけて行われた群論に関する未発表の講義の中で、ケイリーグラフを「グループ図」（Gruppenbild）という名前で再導入し、これが今日の幾何学的群論へと繋がった。彼の最も重要な応用は、種数2以上の 曲面 の 基本群 に関する 語問題 の解法であり、これは曲面上のどの閉曲線が点に縮約するかを決定する位相問題と等価である。 [11]
参照 ^ 証明： を色付き有向グラフ の任意の自己同型とし 、 を 恒等グラフ の像とする。 から の辺距離に関する帰納法によって、 すべての に対してが成り立つことを示す 。 と仮定する 。この自己同型は、任意の 色の辺 を別の 色の辺に 繋ぐ 。したがって となり 、帰納法は続く。 は連結なので、 すべての に対して が成り立つ 。 σ : V ( Γ ) → V ( Γ ) {\displaystyle \sigma :V(\Gamma )\to V(\Gamma )} Γ {\displaystyle \Gamma } h = σ ( e ) {\displaystyle h=\sigma (e)} σ ( g ) = h g {\displaystyle \sigma (g)=hg} g ∈ V ( Γ ) {\displaystyle g\in V(\Gamma )} g {\displaystyle g} e {\displaystyle e} σ ( g ) = h g {\displaystyle \sigma (g)=hg} σ {\displaystyle \sigma } c s {\displaystyle c_{s}} g → g s {\displaystyle g\to gs} c s {\displaystyle c_{s}} σ ( g ) → σ ( g s ) {\displaystyle \sigma (g)\to \sigma (gs)} σ ( g s ) = σ ( g ) s = h g s {\displaystyle \sigma (gs)=\sigma (g)s=hgs} Γ {\displaystyle \Gamma } σ ( g ) = h g {\displaystyle \sigma (g)=hg} g ∈ V ( Γ ) {\displaystyle g\in V(\Gamma )} ^ 対称群が と同型である単純なグラフ (色なし、無向) に 簡単に変更できます 。 の色付き有向エッジを、 色に対応する適切なツリーに置き換えます。 Γ {\displaystyle \Gamma } G {\displaystyle G} Γ {\displaystyle \Gamma }
注記 ^ ab マグナス, ウィルヘルム ; カラス, アブラハム; ソリター, ドナルド (2004) [1966]. 組合せ群論：生成元と関係による群の表現. クーリエ. ISBN 978-0-486-43830-6 。 ^ ab Cayley, Arthur (1878). 「要望と提案：第2号 群論：グラフィカル表現」 . American Journal of Mathematics . 1 (2): 174–6 . doi :10.2307/2369306. JSTOR 2369306. 『数学論文集』10:403-405頁。 ^ セロン、ダニエル・ピーター (1988). グラフィカル正則表現の概念の拡張 (博士論文). ウィスコンシン大学マディソン校. p. 46. MR 2636729. 。 ^ Bartholdi, Laurent (2017). 「群の成長と花輪積」. Ceccherini-Silberstein, Tullio; Salvatori, Maura; Sava-Huss, Ecaterina (編). 群、グラフ、ランダムウォーク：2014年6月2日～6日にコルトーナで開催されたワークショップからの選抜論文 . London Math. Soc. Lecture Note Ser. Vol. 436. Cambridge Univ. Press, Cambridge. pp. 1– 76. arXiv : 1512.07044 . ISBN 978-1-316-60440-3 . MR 3644003。 ^ サビドゥッシ, ゲルト (1958年10月). 「固定小数点フリーグラフのクラスについて」. アメリカ数学会誌 . 9 (5): 800–4 . doi : 10.1090/s0002-9939-1958-0097068-7 . JSTOR 2033090. ^ Babai, László (1995) の定理 3.7 を参照。 「27. 自己同型群、同型、再構成」 (PDF) 。グラハム 、ロナルド L. ; マーティン・グレッシェル ; ロヴァース、ラーズロ (編)。組み合わせ論のハンドブック。 Vol. 1.エルゼビア。ページ 1447–1540。ISBN 9780444823465 。 ^ White, Arthur T. (1972). 「群の種数について」. アメリカ数学会誌 . 173 : 203–214 . doi : 10.1090/S0002-9947-1972-0317980-2 . MR 0317980. ^ 命題1.12、 Lubotzky, Alexander (2012). 「純粋数学と応用数学におけるエクスパンダーグラフ」 アメリカ数学会報 . 49 : 113–162 . arXiv : 1105.2389 . doi : 10.1090/S0273-0979-2011-01359-3 . ^ abc Ahmady, Azhvan; Bell, Jason; Mohar, Bojan (2014). 「Integral Cayley graphs and groups」. SIAM Journal on Discrete Mathematics . 28 (2): 685– 701. arXiv : 1307.6155 . doi :10.1137/130925487. S2CID 207067134. ^ Guo、W.;リトキナ、DV;マズロフ、バージニア州。レビン、DO (2019)。 「積分ケイリーグラフ」 (PDF) 。 代数と論理 。 58 (4 ) : 297–305。arXiv : 1808.01391 。 土井 ：10.1007/s10469-019-09550-2。 S2CID 209936465。 ^ デーン、マックス (2012) [1987]. 群論と位相幾何学に関する論文 . シュプリンガー・フェアラーク. ISBN 978-1461291077 。 ドイツ語から翻訳され、ジョン・スティルウェル による序文と付録、 オットー・シュライアー による付録が付いています 。
外部リンク 
![{\displaystyle [\rho _{\text{reg}}(g)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ae6913fec143b738c35b6c0cdab5043828b419d)
![{\textstyle A=\sum _{s\in S}[\rho _{\text{reg}}(s)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8555779d750b60e0a8cc56900d52743f5ff8719d)
