ケーリーグラフとして実現出来る多面体グラフ

今日はグラフ理論の話題について書いてみます。自分で考えたことではなくって、ふと思い立って検索してみたら知りたかった事実について書かれているページを発見したのでおすそ分け、といった感じです。

グラフ理論とはグラフと呼ばれる「いくつかの点をいくつかの線で結んだような図で表現されるもの」を扱う分野です。NOTE でも色々な記事があるので、いくつかリンクを張っておきます。

グラフの作り方の一つにケーリーグラフというものがあります。これは群を利用して作られる対称性の高いグラフで、次のように作ります。

1. 有限群 $${G}$$ を持ってくる。$${G}$$ の元の個数を $${n}$$ としておく。

2. $${G}$$ の部分集合 $${S}$$ であって、以下の条件を満たすものを選ぶ：
   (1) $${s\in S}$$ ならば $${s^{-1}\in S}$$ を満たす。
   (2) $${S}$$ は $${G}$$ を生成する、つまり $${G}$$ の任意の元は $${S}$$ の元のいくつかの積として表すことができる。

3. 点を $${n}$$ 個用意し、それらに $${G}$$ の元で名前を付けておく（抽象的に考えるならば $${G}$$ を頂点集合とするということ）。

4. 次のルールで辺を結ぶ：$${x, y\in G}$$ に対して、$${x^{-1}y\in S}$$ ならば $${x}$$ と $${y}$$ に対応する頂点を辺で結ぶ。

こうして出来るグラフは、$${k=|S|}$$ とすれば $${k}$$-正則な連結グラフになります。

簡単な例として、$${G}$$ として位数 $${n}$$ の巡回群を取り、$${a}$$ を $${G}$$ の生成元の一つとして $${S=\{a,a^{-1}\}}$$ とすると、こうして定まるケーリーグラフは $${n}$$ 個の頂点を持つサイクルグラフになります（少し具体的に書くと、頂点に $${0,1,\dots,n-1}$$ と番号を振っておき、$${y-x\equiv\pm1 \pmod n}$$ ならば $${x}$$ 番の頂点と $${y}$$ 番の頂点を辺で結ぶ、という風にして作られるグラフです）。

さてここからが本題です。ケーリーグラフの具体例をいくつか見ていると、正四面体グラフや立方体グラフといった正多面体グラフがケーリーグラフとして実現されることに気づきます。確かに正多面体グラフは対称性が高い正則グラフなので、ケーリーグラフとして実現出来ても不思議では無いような気がします。そうすると、正多面体グラフ、あるいは少し一般化して半正多面体グラフのうちでケーリーグラフとして実現出来るものはどれぐらいあるのかな、という問いが浮かびます。

わりと自然な問いかけなので、きっと知られているだろうと思って検索してみると、ありました、次のようなページを見つけました。

Cayley Graphs

このページによると、正多面体および半正多面体のうちで、正十二面体 (dodecahedron) と二十・十二面体 (icosidodecahedron) の二つ以外の多面体に対して、その多面体グラフはケーリーグラフとして実現出来るのだそうです。思いのほか多くの（半）正多面体グラフがケーリーグラフになっていて、ちょっとびっくりです。

ちなみに、実現出来ない二つの場合のうち、正十二面体グラフがケーリーグラフとして表せないことの証明は上のページにあります。私はまだちゃんと考えていないのですが、もう一つの二十・十二面体グラフの場合の証明も同様なのでしょうか？

あと、上のページでは実現可能な場合に $${S}$$ としてどのような集合をとれば良いかも具体的に書かれています。この情報を使えば SAGE でケーリーグラフとして実際に実現されることを確かめられます。たとえば正二十面体グラフであれば、次のようなコードを SageMathCell で実行すればOK。

S = [[(1,2,3)], [(2,3,4)], [(1,3),(2,4)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(edge_size=0.01)

一番頂点数の多い斜方切頂二十・十二面体 (rhombitruncated icosidodecahedron) グラフの場合のコードは次のような感じ（頂点数が多いので、見た目がほどよくなるまでの調整回数を iterations=500 というオプションで増やしています）。

S = [[(1,2),(4,7),(5,11),(9,12)], [(3,6),(4,5),(7,11),(8,10)], [(2,3),(4,6),(8,11),(9,10)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)

以下、自分用に SageMath コードのメモ。

# Tetrahedron

S = [[(1,2),(3,4)], [(1,3),(2,4)], [(1,4),(2,3)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Cube

S = [[(1,2,3,4)], [(1,3)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Octahedron

S = [[(1,2,3)], [(1,2)], [(2,3)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Dodecahedron : impossible


# Icosahedron

S = [[(1,2,3)], [(2,3,4)], [(1,3),(2,4)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Truncated Tetrahedron

S = [[(1,2,3)], [(1,2),(3,4)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Cuboctahedron

S = [[(1,2,3)], [(2,3,4)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Truncated Cube

S = [[(1,2,3)], [(3,4)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Truncated Octahedron

S = [[(1,2,3,4)], [(1,2)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Rhombicuboctahedron

S = [[(1,2,3,4)], [(1,2,3)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Rhombitruncated Cuboctahedron

S = [[(1,2),(4,5)], [(1,3),(4,6)], [(2,5)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Snub Cuboctahedron

S = [[(1,2,3,4)], [(1,2,3)], [(3,4)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Icosidodecahedron : impossible


# Truncated Dodecahedron

S = [[(1,2,4)], [(2,3),(4,5)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Truncated Icosahedron

S = [[(1,2,3,4,5)], [(2,3),(4,5)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Rhombicosidodecahedron

S = [[(1,2,3,4,5)], [(1,2,4)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Snub Icosidodecahedron

S = [[(1,2,3,4,5)], [(1,2,4)], [(2,3),(4,5)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Prism

S = [[(1,2,3,4,5,6,7)], [(1,7),(2,6),(3,5)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)


# Anti-prism

S = [[(1,2,3,4,5,6,7)], [(1,7),(2,6),(3,5)], [(2,7),(3,6),(4,5)]]
G = PermutationGroup(S)
G.cayley_graph().to_simple().show3d(iterations=500, edge_size=0.01)

（5/31 に修正：文中の誤字を直しました。SageMath のコードに to_simple() を加えて無向グラフとして表示する（辺を矢印ではなく線分で表す）ようにしました。自分用のメモを追記しました。）