講演スライド

最小固有値 −2 を持つグラフと
ルート系
宗政昭弘
東北大学大学院情報科学研究科
2010 年 10 月 9 日 九州大学
研究集会「Magma で広がる数学の世界」
Combinatorics → Graphs → Introduction
ここでは簡単のため、向きのない単純グラフのみを扱う。
Def. グラフとは有限集合 V と V の２点部分集合いくつかからなる
族 E の組 (V, E) のことである。すなわち
|V | < ∞,
E ⊂ {{x, y} | x, y ∈ V, x 6= y}.
V の要素は「点」とよび、E の要素は「辺」とよぶ。
Ex. V = {1, 2, 3}, E = {{1, 2}, {2, 3}}. Magma では
Graph<{1,2,3}|{{1,2},{2,3}}>;
で定義できる。または、もっと簡単に
PathGraph(3);
でもよい。
代表的なグラフと標準的な構成法 (I)
完全グラフ
G:=CompleteGraph(4);
サイクル
G:=PolygonGraph(4);
補グラフ
Complement(G);
（Magma にはグラフを描く機能はありません）
代表的なグラフと標準的な構成法 (II)
Def. グラフ G の ライングラフ（line graph） とは、G の辺を新た
に点と考えて、それらが共有点をもつときに新たに辺で結んだもの。
LineGraph(G);
グラフ隣接行列と固有値
Magma のマニュアルでは Basic Rings and Linear Algebra → Matrices
Def. グラフ G の 隣接行列（adjacency matrix） とは、G の頂点集
合 V で添字付けられている n × n 行列（n = |V |）で、成分が
(
1 x と y は辺で結ばれているとき,
Ax,y =
0 そうでないとき.
V の並べ方によって行列は一意的に決まらないが、行と列の同時置換
を除いて定まる。この行列 A の固有値を単にグラフ G の固有値と
よぶ。
A:=AdjacencyMatrix(G);
デモ 1
グラフの最小固有値は必ず実数で代数的整数
• 固有値は一般には整数とは限らない。
• 固有値の計算は行列成分の属している環を指定すると、その環に
属す固有値のみが計算される（多項式の因数分解も、係数環を指
定しておくのでそこで分解するのと同じ）。
• 係数環として実数体を指定すれば近似計算される。
• 係数環として分解体を指定しても分解体の実数体への埋め込みま
で指定したことにはならないので注意が必要。
A:=AdjacencyMatrix(G);
Eigenvalues(A);
デモ 2 Global Arithmetic Fields → Quadratic Fields
なぜ最小固有値に注目するか
Def. グラフ G のノルム m 表現とは、G の頂点集合から Rn への単
射 ϕ で、ある正整数 m が存在して


m x = y のとき,
(ϕ(x), ϕ(y)) = 1 x と y は辺で結ばれているとき,


0 それ以外.
G の隣接行列を A とすると、G がノルム m 表現をもつ ⇐⇒
A + mI が非負値 ⇐⇒ G の最小固有値が m 以上。
最小固有値がある値以上であるかを問題にするので、最小固有値を
はっきり求める必要はない。また、これから主に扱うグラフは最小固
有値がちょうど −2 である。
IsPositiveSemiDefinite(A+m*I);
デモ 3
最小固有値が −2 のグラフはノルム 2 の表現をもつ→ ルート系
ノルム 2 のベクトルからなるユークリッド空間の部分集合で互いの
内積が整数となるものは、
• 鏡映による閉包をとる、（またはこれと同値な ↓）
• 整数係数一次結合で表されるノルム 2 のベクトルをすべて付加
という操作で、鏡映による閉包で閉じている「ルート系」という分類
されたもののどれかになる。
G があるグラフのライングラフ
=⇒ G の最小固有値 ≥ −2
⇐⇒ A + 2I は非負値行列,
=⇒ グラフ G はノルム 2 の表現をもつ
グラフ G はルート系 An , Dn , En の部分集合で表現される
（ただし G が連結なら）
ルート系
Magma においてルート系は
Lie Theory → Root Systems または
Lattices and Quadratic Forms → Lattices
で利用できる。
最小固有値 −2 をもつグラフの表現は、その隣接行列 A を用いて、
A + 2I をグラム行列とするユークリッド空間の部分集合のことであ
る。この部分集合で生成された lattice が何であるか Magma で計算
できる。
Ex. ５点の完全グラフのライングラフの補グラフ L(K5 ) は最小固有
値 −2 であり、このグラフをノルム 2 で表現した集合は E6 root
lattice を生成する。（デモ 4）
最小固有値 −2 をもつグラフをルート系から逆に作る
逆に、L(K5 ) をルート系 E6 の中に作れる。
• E6 ルート系 72 点からなるグラフをつくる（内積が 1 のとき辺
で結ぶが、E6 全体では負の内積があるので、１つのグラフの表
現の像ではない）。
E6short:=ShortestVectors(Lattice("E",6));
#E6short eq 36;
E6:=&join{{x,-x}:x in E6short};
#E6 eq 72;
E6graph:=Graph<E6|{{x,y}:x,y in E6|(x,y) eq 1}>;
V:=Vertices(E6graph);
• １つの頂点 a を任意の近傍 N は |N | = 20 であり、
[
N = {b ∈ E6 | (a, b) = 1} =
{b, a − b} 10 個の和集合
b∈N
E6 における１点 a の近傍 = N
N = {b ∈ E6 | (a, b) = 1} =
[
{b, a − b}
10 個の和集合
b∈N
a:=Random(E6);
N:={b:b in E6|(a,b) eq 1};
#N eq 20;
NN:={{b,a-b}:b in N};
#NN eq 10;
これら 10 個の組のうち、うまく片方だけ選ぶと L(K5 ) ができる。
C:=CartesianProduct(Setseq(NN));
#C eq 2^10;
Gs:={sub<E6graph|{V|c[i]:i in {1..10}}>:c in C};
G:=Complement(LineGraph(CompleteGraph(5)));
&or{IsIsomorphic(G,H):H in Gs};
最小固有値が −2 以上のグラフは特別なのか
• ノルム 2 の表現が生成する root lattice が An (n ≥ 2) であるよ
うなグラフ、Dn (n ≥ 4) であるようなグラフは無限にあるが、
それらの構造的な特徴付けがある（ライングラフとその一般化）。
• En (n = 6, 7, 8) についてはグラフ自体有限個しかなく、それら
の構造的な特徴付けは知られていない。
• 有限個しかないのだからとりあえず分類して、それらの性質を調
べてみてはどうか。
• 極大なものを分類すれば、他はそれらの部分グラフになって
いる。
Def. グラフ G が maximal exceptional graph とは、G がノルム 2
の表現 ϕ を E8 ルート系にもち、
∀a ∈ E8 , a ∈
/ ϕ(G) に対して, ∃x ∈ ϕ(G), (a, x) < 0.
となるときをいう。
Maximal Exceptional Graph の分類
Theorem (Kitazume–M. (unpublished)). G を maximal exceptional
graph とし、X = ϕ(G) ⊂ E8 を G のノルム 2 の表現 ϕ による像と
すると、次のいずれかが成り立つ。
(i). ∃a1 , . . . , a6 ∈ X, (ai , aj ) = 0 (i 6= j),
(ii). ∃a ∈ X, |{b ∈ X | (a, b) = 1}| = 28.
(ii) の意味：
N = {b ∈ E8 | (a, b) = 1}
とおくと |N | = 56 で
[
N=
{b, a − b}
b∈N
(28 個の和集合)
↑ 両方は同時に X の元としてとれない。
Maximal Exceptional Graph の分類 (X ⊂ E8 )
(i). ∃a1 , . . . , a6 ∈ X, (ai , aj ) = 0 (i 6= j),
(ii). ∃a ∈ X, |{b ∈ X | (a, b) = 1}| = 28.
[
N=
{b, a − b} (28 個の和集合)
b∈N
• (i) の分類は簡単で、Magma を使わず理論的にできる。
• (ii) の分類は、228 個のグラフを分類しなければならない。（経験
的な目安として Magma 内で size 223 個の（例えばベクトル）
の集合を作るのに memory 1GB ぐらい必要。228 だと 32GB）
E8 ルート系の鏡映群における a の安定部分群（すなわち E7 ルート
系の鏡映群）が作用しているので、その作用で軌道分解する。
W (E7 ) の 228 次の置換群としての軌道分解（代表元を見つけること）
• 直接はできないので、W (E7 ) の部分群である W (D6 ) を使う。
• W (D6 ) は 228 点上には 216 × 212 という直積への作用をしている
ので、216 , 212 それぞれ軌道分解する（これならメモリ不足には
ならない）。
• W (D6 ) による軌道の代表元から、W (E7 ) で同値なものを捨てる
このようにして 467 個の代表元が得られる。(i) と合わせて 473 個。
Cvetković–Lepović–Rowlinson–Simić (2002) による、全く別の計
算方法による分類結果と一致。
分類できる範囲だとなぜわかったか。
28
2
= 93
デモ 5
|W (E7 )|