ケーリーグラフ

数学において、ケイリーグラフはケイリーカラーグラフ、ケイリー図、群図、またはカラー群とも呼ばれ、^[1]グループの抽象的な構造をエンコードしたグラフです。その定義はケイリーの定理(アーサー・ケイリーにちなんで名付けられました)によって示唆され、グループの特定の生成子セットを使用します。これは、組合せ群論および幾何群論の中心的なツールです。ケイリーグラフの構造と対称性により、エクスパンダーグラフの構築に特に適しています。

を群とし、を生成集合とする。ケイリーグラフは、次のように構成される辺色有向グラフである。^[2]${\displaystyle G}$${\displaystyle S}$${\displaystyle G}$${\displaystyle \Gamma =\Gamma (G,S)}$

• の各要素には頂点が割り当てられます。 の頂点集合は次のように識別されます。${\displaystyle g}$${\displaystyle G}$${\displaystyle \Gamma}$${\displaystyle G.}$
• の各要素には色が割り当てられます。${\displaystyle s}$${\displaystyle S}$${\displaystyle c_{s}}$
• およびごとに、 に対応する頂点から に対応する頂点へ、の有向辺が存在します。${\displaystyle g\in G}$${\displaystyle s\in S}$${\displaystyle c_{s}}$${\displaystyle g}$${\displaystyle gs}$

すべての規則で が群を生成することが必要なわけではありません。が の生成集合でない場合、 は切断され、各連結成分は によって生成される部分群の剰余類を表します。 ${\displaystyle S}$${\displaystyle S}$${\displaystyle G}$${\displaystyle \Gamma}$${\displaystyle S}$

の要素がそれ自身の逆である場合、それは通常、無向辺によって表されます。 ${\displaystyle s}$${\displaystyle S}$${\displaystyle s=s^{-1},}$

集合は有限であると仮定されることが多く、特に幾何群論では有限であることが想定され、これは局所有限であることと有限生成であることに対応します。 ${\displaystyle S}$${\displaystyle \Gamma}$${\displaystyle G}$

集合は対称( ) であり、グループの単位元を含まないと想定されることがあります。この場合、色付けされていないケイリーグラフは単純な無向グラフとして表すことができます。 ${\displaystyle S}$${\displaystyle S=S^{-1}}$

• が無限巡回群であり、その集合が標準生成元 1 とその逆元 (加法表記では -1) から構成されると仮定すると、ケイリー グラフは無限パスになります。${\displaystyle G=\mathbb {Z} }$${\displaystyle S}$
• 同様に、が の有限巡回群であり、集合がの標準生成元とその逆元の 2 つの要素で構成される場合、ケイリー グラフは巡回グラフ です。より一般的には、有限巡回群のケイリー グラフはまさに巡回グラフです。${\displaystyle G=\mathbb {Z} _{n}}$${\displaystyle n}$${\displaystyle S}$${\displaystyle G}$ ${\displaystyle C_{n}}$
• 群の直積（生成集合の直積を生成集合とする）のケイリーグラフは、対応するケイリーグラフの直積である。 ^[3]したがって、 4つの要素からなる生成子の集合を持つ アーベル群のケイリーグラフは平面上の無限グリッドであるが、同様の生成子を持つ直積の場合、ケイリーグラフはトーラス上の有限グリッドである。${\displaystyle \mathbb {Z} ^{2}}$${\displaystyle (\pm 1,0),(0,\pm 1)}$${\displaystyle \mathbb {R} ^{2}}$${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{m}}$${\displaystyle n\times m}$

• 2 つの生成元と上の二面体群 のケイリー グラフが左側に示されています。赤い矢印は との合成を表しています。は自己逆なので、 との合成を表す青い線は無向です。したがって、グラフは混合グラフです。つまり、8 つの頂点、8 つの矢印、4 つの辺があります。群のケイリー表は、群の表示から導出できます。の別のケイリー グラフが右側に示されています。は依然として水平反射であり、青い線で表され、 は対角反射であり、ピンクの線で表されます。両方の反射が自己逆なので、右側のケイリー グラフは完全に無向です。このグラフは、表示に対応しています。${\displaystyle D_{4}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$${\displaystyle D_{4}}$ $${\displaystyle \langle a,b\mid a^{4}=b^{2}=e,ab=ba^{3}\rangle .}$$${\displaystyle D_{4}}$${\displaystyle b}$${\displaystyle c}$$${\displaystyle \langle b,c\mid b^{2}=c^{2}=e,bcbc=cbcb\rangle .}$$
• 2 つの生成元と 上の自由群のケイリー グラフは、集合 に対応しており、 は恒等関数として、この記事の先頭に示されています。右への辺に沿って移動することは による右乗算を表し、上への辺に沿って移動することは による乗算に対応します。自由群には関係 がないため、ケイリー グラフにはサイクルがありません。これは 4 次正則無限木です。これは、バナッハ-タルスキーのパラドックスの証明における重要な要素です。${\displaystyle a}$${\displaystyle b}$${\displaystyle S=\{a,b,a^{-1},b^{-1}\}}$${\displaystyle e}$${\displaystyle a,}$${\displaystyle b.}$
• より一般的には、ベーテ格子またはケイリー木は、生成元上の自由群のケイリーグラフです。生成元による群の表現は、生成元上の自由群からケイリー木から のケイリーグラフへの写像を定義する群への射影準同型に対応します。グラフを1 次元単体複体として位相的に解釈すると、単連結無限木はケイリーグラフの普遍被覆であり、写像の核はケイリーグラフの基本群です。${\displaystyle n}$${\displaystyle G}$${\displaystyle n}$${\displaystyle n}$${\displaystyle G,}$${\displaystyle G}$

• 離散ハイゼンベルク群 のケーリーグラフを右に描いています。図で使用されている生成元は、要素 に対する 1, 0, 0 の 3 つの順列によって与えられる3 つの行列です。これらは関係 を満たしており、これも図から理解できます。これは非可換無限群であり、3 次元空間であるにもかかわらず、ケーリーグラフは 4 次元の体積成長を持ちます。^[4]$${\displaystyle \left\{{\begin{pmatrix}1&x&z\\0&1&y\\0&0&1\\\end{pmatrix}},\ x,y,z\in \mathbb {Z} \right\}}$$${\displaystyle X,Y,Z}$${\displaystyle x,y,z}$${\displaystyle Z=XYX^{-1}Y^{-1},XZ=ZX,YZ=ZY}$

群は左乗算によって自身に作用する（ケーリーの定理を参照）。これは のケーリーグラフへの作用とみなすことができる。明示的には、要素は頂点を頂点 に写像する。ケーリーグラフの辺の集合とその色はこの作用によって保存される。辺 は辺 に写像され、両方とも色 を持つ。実際、色付き有向グラフ のすべての自己同型はこの形式であるため、 はの対称群と同型である。^{[注 1] [注 2]}${\displaystyle G}$ ${\displaystyle G}$${\displaystyle h\in G}$${\displaystyle g\in V(\Gamma )}$${\displaystyle hg\in V(\Gamma ).}$${\displaystyle (g,gs)}$${\displaystyle (hg,hgs)}$${\displaystyle c_{s}}$${\displaystyle \Gamma }$${\displaystyle G}$${\displaystyle \Gamma }$

群のそれ自身への左乗法作用は単純に推移的であり、特にケイリーグラフは頂点推移的である。以下はこれの逆の一種である。

ラベルなし有向グラフ から群と生成集合を復元するには、頂点を 1 つ選択し、群の単位元でラベルを付けます。次に、 の各頂点に、 をマップする の一意の元でラベルを付けます。 の生成元の集合は、となるため、ケイリー グラフはの外隣接 のラベルの集合です。 は色付けされていないため、 の左乗算マップよりも多くの有向グラフ自己同型を持つ可能性があります。 たとえば、 のグループ自己同型はを並べ替えます。${\displaystyle G}$${\displaystyle S}$${\displaystyle \Gamma }$${\displaystyle v_{1}\in V(\Gamma )}$${\displaystyle v}$${\displaystyle \Gamma }$${\displaystyle G}$${\displaystyle v_{1}}$${\displaystyle v.}$${\displaystyle S}$${\displaystyle G}$${\displaystyle \Gamma }$${\displaystyle \Gamma (G,S)}$${\displaystyle v_{1}}$${\displaystyle \Gamma }$${\displaystyle G}$${\displaystyle S}$

• ケイリーグラフは、生成元集合の選択に本質的に依存する。例えば、生成元集合に要素がある場合、ケイリーグラフの各頂点には入ってくる有向辺と出ていく有向辺がある。要素を持つ対称生成元集合の場合、ケイリーグラフは次数の正則有向グラフである。${\displaystyle \Gamma (G,S)}$${\displaystyle S}$${\displaystyle S}$${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle S}$${\displaystyle r}$${\displaystyle r.}$
• ケイリーグラフのサイクル（または閉じたウォーク）は、 の要素間の関係を示します。 グループのケイリー複合体のより精巧な構築では、関係に対応する閉じたパスが多角形によって「埋められます」。 これは、与えられた表現のケイリーグラフを構築する問題は、の単語問題を解くことと同等であることを意味します。^[1]${\displaystyle S.}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {P}}}$
• が全射群準同型であり、の生成集合の元の像が異なる場合、のグラフの被覆が誘導されます。特に、グループにすべての次数が 2 と異なる生成元があり、集合がこれらの生成元とその逆生成元で構成される場合、ケイリー グラフは同じ生成元集合上の自由群に対応する次数の無限正規木によって覆われます。${\displaystyle f:G'\to G}$ ${\displaystyle S'}$${\displaystyle G'}$$${\displaystyle {\bar {f}}:\Gamma (G',S')\to \Gamma (G,S),}$$${\displaystyle S=f(S').}$${\displaystyle G}$${\displaystyle k}$${\displaystyle S}$${\displaystyle \Gamma (G,S)}$${\displaystyle 2k}$
• 無向グラフとみなされる有限ケイリーグラフでは、頂点の接続性は少なくともグラフの次数の 2/3 に等しい。生成集合が最小の場合 (生成集合から任意の要素と、存在する場合はその逆要素を除去すると、生成しない集合が残る)、頂点の接続性は次数に等しい。辺の接続性は、すべての場合において次数に等しい。^[6]
• が で示される行列形式を持つ左正規表現である場合、 の隣接行列はです。${\displaystyle \rho _{\text{reg}}(g)(x)=gx}$${\displaystyle |G|\times |G|}$${\displaystyle [\rho _{\text{reg}}(g)]}$${\displaystyle \Gamma (G,S)}$${\textstyle A=\sum _{s\in S}[\rho _{\text{reg}}(s)]}$
• 群のすべての群特性は 、 の隣接行列の固有ベクトルを誘導します。関連付けられた固有値は で、 がアーベルのとき、整数に対して の形を取ります。特に、自明な特性 (すべての要素を 1 にする特性) の関連付けられた固有値は の次数、つまり の位数です。 がアーベル群の場合、特性はちょうど 個あり、すべての固有値を決定します。対応する固有ベクトルの正規直交基底は で与えられます。この固有基底が生成集合 に依存しない点は興味深いことです。${\displaystyle \chi }$${\displaystyle G}$${\displaystyle \Gamma (G,S)}$$${\displaystyle \lambda _{\chi }=\sum _{s\in S}\chi (s),}$$${\displaystyle G}$$${\displaystyle \sum _{s\in S}e^{2\pi ijs/|G|}}$$${\displaystyle j=0,1,\dots ,|G|-1.}$${\displaystyle \Gamma (G,S)}$${\displaystyle S}$${\displaystyle G}$${\displaystyle |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}}.}$${\displaystyle S}$
  より一般的には、対称生成集合について、の既約表現の完全な集合を取り、 を固有値集合 とします。すると、 の固有値の集合は、がの固有値として出現するたびに、が重複して出現するまさにその場所です。${\displaystyle \rho _{1},\dots ,\rho _{k}}$${\displaystyle G,}$${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$${\displaystyle \Lambda _{i}(S)}$${\displaystyle \Gamma (G,S)}$${\textstyle \bigcup _{i}\Lambda _{i}(S),}$${\displaystyle \lambda }$${\displaystyle \dim(\rho _{i})}$${\displaystyle \lambda }$${\displaystyle \rho _{i}(S).}$

代わりに、頂点を固定された部分群の右剰余類とすると、関連する構成であるシュライア剰余類グラフが得られ、これは剰余類列挙またはトッド・コクセター過程の基礎となります。 ${\displaystyle H,}$

群の構造についての知識は、グラフの隣接行列を調べ、特にスペクトルグラフ理論の定理を適用することによって得ることができる。逆に、対称生成集合の場合、のスペクトル理論と表現理論は直接結びついている。つまり、の既約表現の完全な集合を取り、を固有値とする。すると、の固有値の集合は、が の固有値として出現するたびに、固有値が重複して現れるまさにその場所である。${\displaystyle \Gamma (G,S)}$${\displaystyle \rho _{1},\dots ,\rho _{k}}$${\displaystyle G,}$${\textstyle \rho _{i}(S)=\sum _{s\in S}\rho _{i}(s)}$${\displaystyle \Lambda _{i}(S)}$${\displaystyle \Gamma (G,S)}$${\textstyle \bigcup _{i}\Lambda _{i}(S),}$${\displaystyle \lambda }$${\displaystyle \dim(\rho _{i})}$${\displaystyle \lambda }$${\displaystyle \rho _{i}(S).}$

群の種数とは、その群の任意のケイリーグラフの最小の種数である。[ 7 ^]

無限群の場合、ケーリーグラフの粗い幾何学は幾何学群論の基礎となります。有限生成群の場合、これは生成元の有限集合の選択とは無関係であり、したがって群の固有の特性です。これは無限群の場合にのみ興味深いものです。すべての有限群は点 (または自明群) と粗く同値です。これは、生成元の有限集合として群全体を選択できるためです。

正式には、与えられた生成元に対して、メトリック（ケイリーグラフ上の自然距離）という言葉があり、これによってメトリック空間が決定されます。この空間の粗同値類は、群の不変量です。

のとき、ケイリーグラフは-正則なので、スペクトル手法を使用してグラフの展開特性を分析できます。特にアーベル群の場合、ケイリーグラフの固有値はより簡単に計算でき、 によって与えられ、上側の固有値は に等しいので、チェーガーの不等式を使用して、スペクトルギャップを使用してエッジ展開比を制限できます。 ${\displaystyle S=S^{-1}}$${\displaystyle \Gamma (G,S)}$${\displaystyle |S|}$${\textstyle \lambda _{\chi }=\sum _{s\in S}\chi (s)}$${\displaystyle |S|}$

表現論は、カズダン性質（T）の形でそのような拡張ケイリーグラフを構築するために使用することができます。次のステートメントが成り立ちます：^[8]

離散群がカジダンの性質 (T) を持ち、 の有限対称生成集合である場合、のみに依存する定数が存在し、の像に対する のケイリーグラフの任意の有限商に対して は-展開子となります。${\displaystyle G}$${\displaystyle S}$${\displaystyle G}$${\displaystyle c>0}$${\displaystyle G,S}$${\displaystyle Q}$${\displaystyle G}$${\displaystyle Q}$${\displaystyle S}$${\displaystyle c}$

たとえば、グループは特性 (T) を持ち、基本行列によって生成され、これにより拡張グラフの比較的明示的な例が得られます。 ${\displaystyle G=\mathrm {SL} _{3}(\mathbb {Z} )}$

積分グラフとは、固有値がすべて整数であるグラフです。積分グラフの完全な分類は未解決の問題ですが、特定のグループのケイリー グラフは常に積分です。ケイリー グラフのスペクトルの以前の特徴付けを使用すると、 が積分であるためには、の固有値が のすべての表現に対して積分である必要があることに注意してください。 ${\displaystyle \Gamma (G,S)}$${\displaystyle \rho (S)}$${\displaystyle \rho }$${\displaystyle G}$

群がケイリー積分単純 (CIS) であるとは、対称生成集合がの部分群の補集合であるときに連結ケイリーグラフが整列していることを意味する。Ahmady、Bell、Mohar の結果は、すべての CIS 群が、または素数 に対してと同型であることを示している。^[9]ケイリーグラフが連結であるためには、が実際に群全体を生成することが重要である。(が を生成しない場合、ケイリーグラフは依然として整列している可能性があるが、 の補集合は必ずしも部分群ではない。) ${\displaystyle G}$${\displaystyle \Gamma (G,S)}$${\displaystyle S}$${\displaystyle G}$${\displaystyle \mathbb {Z} /p\mathbb {Z} ,\mathbb {Z} /p^{2}\mathbb {Z} }$${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{2}}$${\displaystyle p}$${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$

の例では、対称生成集合（グラフ同型性を除く）は ${\displaystyle G=\mathbb {Z} /5\mathbb {Z} }$

• ${\displaystyle S=\{1,4\}}$:は固有値を持つ閉路である${\displaystyle \Gamma (G,S)}$${\displaystyle 5}$${\displaystyle 2,{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}},{\tfrac {-{\sqrt {5}}-1}{2}}}$
• ${\displaystyle S=\{1,2,3,4\}}$:固有値を持つ${\displaystyle \Gamma (G,S)}$${\displaystyle K_{5}}$${\displaystyle 4,-1,-1,-1,-1}$

の唯一の部分群は、全体群と自明群であり、積分グラフを生成する唯一の対称生成集合は、自明群の補集合です。したがって、 はCIS 群である必要があります。 ${\displaystyle \mathbb {Z} /5\mathbb {Z} }$${\displaystyle S}$${\displaystyle \mathbb {Z} /5\mathbb {Z} }$

完全なCIS分類の証明は、CIS群のすべての部分群と準同型像もCIS群であるという事実を利用している。^[9]

少し異なる概念は、ケーリー積分群の概念であり、この群では、すべての対称部分集合が積分グラフを生成します。は、もはや群全体を生成しなくてもよいことに注意してください。 ${\displaystyle G}$${\displaystyle S}$${\displaystyle \Gamma (G,S)}$${\displaystyle S}$

ケーリー積分群の完全なリストは、および の位数の二環式群で与えられ、ここでおよび は四元数群である。^[9]証明はケーリー積分群の2つの重要な性質に依存している。 ${\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}}$${\displaystyle 12}$${\displaystyle m,n\in \mathbb {Z} _{\geq 0}}$${\displaystyle Q_{8}}$

• ケーリー整群の部分群と準同型像もケーリー整群である。
• 群がケイリー積分であるためには、その群のすべての連結されたケイリーグラフも積分でなければならない。

一般群 が与えられたとき、部分集合が の元による共役で閉じている場合（正規部分群の概念を一般化）、部分集合 は正規であり、任意の に対して、巡回群を生成する元の集合が にも含まれる場合、オイラーである。Guo、Lytkina、Mazurov、および Revin による 2019 年の成果は、純粋に表現論的な手法を使用して、ケイリーグラフが任意のオイラー正規部分集合 に対して積分であることを証明している。^[10]${\displaystyle G}$${\displaystyle S\subseteq G}$${\displaystyle S}$${\displaystyle G}$${\displaystyle S}$${\displaystyle s\in S}$${\displaystyle \langle s\rangle }$${\displaystyle S}$${\displaystyle \Gamma (G,S)}$${\displaystyle S\subseteq G}$

この結果の証明は比較的短い。オイラー正規部分集合が与えられたとき、 が共役類の和集合となるような非共役なペアを選択する。次に、ケーリーグラフのスペクトルの特徴付けを用いて、 の固有値がの既約指標を取ったによって与えられることを示すことができる。この集合の各固有値は、原始根 1に対しての元でなければならない（ただし は各 の位数で割り切れなければならない）。固有値は代数的整数であるため、それらが整式であることを示すには、それらが有理数であることを示し、の任意の自己同型の下で が固定されていることを示すだけで十分である。すべての に対して となるような、 と互いに素な が存在する必要があり、はオイラー正規であるため、いくつかの に対して となる。共役類を全単射で送るので、 とは同じサイズになり、に対する和の項の順序が変わるだけである。したがって はのすべての自己同型に対して固定されるため、 は有理数であり、したがって整式である。 ${\displaystyle S}$${\displaystyle x_{1},\dots ,x_{t}\in G}$${\displaystyle S}$ ${\displaystyle \operatorname {Cl} (x_{i})}$${\displaystyle \Gamma (G,S)}$${\textstyle \left\{\lambda _{\chi }=\sum _{i=1}^{t}{\frac {\chi (x_{i})\left|\operatorname {Cl} (x_{i})\right|}{\chi (1)}}\right\}}$${\displaystyle \chi }$${\displaystyle G}$${\displaystyle \lambda _{\chi }}$${\displaystyle \mathbb {Q} (\zeta )}$${\displaystyle \zeta }$${\displaystyle m^{th}}$${\displaystyle m}$${\displaystyle x_{i}}$${\displaystyle \lambda _{\chi }}$${\displaystyle \sigma }$${\displaystyle \mathbb {Q} (\zeta )}$${\displaystyle k}$${\displaystyle m}$${\displaystyle \sigma (\chi (x_{i}))=\chi (x_{i}^{k})}$${\displaystyle i}$${\displaystyle S}$${\displaystyle \sigma (\chi (x_{i}))=\chi (x_{j})}$${\displaystyle j}$${\displaystyle x\mapsto x^{k}}$${\displaystyle \operatorname {Cl} (x_{i})}$${\displaystyle \operatorname {Cl} (x_{j})}$${\displaystyle \sigma }$${\displaystyle \lambda _{\chi }}$${\displaystyle \lambda _{\chi }}$${\displaystyle \mathbb {Q} (\zeta )}$${\displaystyle \lambda _{\chi }}$

したがって、が交代群であり、が によって与えられる順列の集合である場合、ケイリー グラフは整列です。(これにより、Kourovka ノートブックの以前の未解決問題が解決されました。) さらに、 が対称群であり、 がすべての転置の集合または特定の要素を含む転置の集合である場合、ケイリー グラフも整列です。 ${\displaystyle G=A_{n}}$${\displaystyle S}$${\displaystyle \{(12i)^{\pm 1}\}}$${\displaystyle \Gamma (A_{n},S)}$${\displaystyle G=S_{n}}$${\displaystyle S}$${\displaystyle \Gamma (G,S)}$

ケイリーグラフは、1878年にアーサー・ケイリーによって有限群に対して初めて考えられました。^[2] マックス・デーンは、 1909年から1910年にかけての群論に関する未発表の講義で、ケイリーグラフをグループ図（群図）という名前で再導入し、これが今日の幾何学的群論につながりました。彼の最も重要な応用は、種数≥2の曲面の基本群に関する単語問題の解決であり、これは曲面上のどの閉曲線が点に収縮するかを決定する位相問題と同等です。^[11]

• 頂点推移グラフ
• グループの生成セット
• ロヴァース予想
• キューブ接続サイクル
• 代数的グラフ理論
• サイクルグラフ（代数）

• ケーリー図
• Weisstein、Eric W.「Cayley グラフ」。MathWorld。