\(k\)色でn個の横一列に並んだ座席を, 隣接する座席は異なる色で彩色するパターンは\(k(k-1)^{n-1}\)通り存在する. これは, 閉区間Iというコンパクト多様体のn個の単体分割Dについて, 彩色パターンが\( k(k-1)^{n-1}\)であると考えることができる. 計量付きコンパクト向きづけ可能曲面Mは有限単体分割Dを持つことはよく知られる (例えば, 小木曽のコンパクトリーマン面の教科書を参照).
Dを\(k\)色で, 隣接する面は異なる色で彩色したもの全体\( Col_D(k)\subset Map(D\rightarrow \{1,\ldots, k\} )\)とする. この集合に, 次の同値関係を入れる.
\(x, y\in Col_D(k)\)が同値とは, ある等長同相写像\( \phi:M\rightarrow M\)で, \(\phi(D)=D\)を満たすもの, すなわち各\(D\)の単体に置換を引き起こすものが存在して, \(x\circ \phi=y:D\rightarrow \{1,\ldots, k\}\)を満たすことをいうとする.
この同値類で割った集合\( Col_{M,D}(k):=Col_D(k)/\sim\)のサイズはどうなるだろうか？
\(Aut(M)\)を等長同相写像全体とする.
\(G:=\{\phi\in Aut(M) \ |\ \phi(D)=D\}\)という群を考える. これは自然な準同型\(G\rightarrow Aut(D)\)を持つ.
以下では、(M,D)の条件として次を仮定する;
(Hyp)\(N:=\ker(G\rightarrow Aut(D))<G\)に対し, ある\(G\)の正規部分群列\(N_0=G>N_1>N_2>\ldots>N_{s-1}>N_s=N\)が存在して, \(N_i/N_{i+1}\)の位数が素数.
例えば、Gがアーベル群の場合はこの仮定が成り立つ。
次の主張を示そう.
Claim; 上述の仮定を満たすM, Dに関して, ある多項式\( P_{M,D}(t)\in \mathbb{Q}[t]\)が存在して,
\( |Col_{M,D}(k)|=P_{M,D}(k)\) が全てのkに対して成立する.
補足;
この多項式は必ずしも整数係数ではない. 同値関係で割らない\(Col_D(k)\)のサイズに関する多項式は存在し(Dのサイズに関する帰納法から示せる)、彩色多項式と呼ぶ.
証明のスケッチ;
\(G\rightarrow Aut(D)\)について,
この像\(P\)は, 特に有限群である. \(P\)は\( X:=Col_{D}(k)\)に作用するので次の無縁和の分解を与えることができる.
\(X=\cup_{x\in R}P\cdot x\)
但し, Rは代表類, 第一に, 次の等式を得る;
\( |X|=\sum_{x \in R} |P|/Stab(x)\)
彩色多項式の存在から, あるkによらない多項式\(P_D(t)\in Q[t]\)が存在して\(|X|=P_D(k)\)であった.
Case 1; |P|が素数pの場合
\(Stab(x)\)の位数は1かpである. 安定化群の位数1,pのRの元全体をそれぞれ\(R_1,R_p\subset R\)とする. 先の等式から
\(P_D(k)=p|R_1|+|R_p|\)
をえる. \(R_p\)は, 全ての\(P\)の\(D\)上の軌道が同じ色で塗られるような彩色である.
\(D\)の面を頂点とし, 隣接する面同士を辺でつなぐグラフ\( X_D\)とする. \(P\)は\(X_D\)に作用すると考えられる. \(P\)の, 各頂点における軌道を頂点全体\(V^{'}\)とし, それぞれの軌道上のいづれかの頂点同士が辺で結ばれるとき, \(\(V^{'}\)の辺とする. このようにしてできるグラフ\(X_{D_p}\)の彩色全体と\(R_p\)は1対1対応する. よって, \(|R_p|=P_{D_p}(k)\)という\(k\)によらない多項式\(P_{D,p}\)が存在する(これは\(X_{D_p}\)の彩色多項式).
以上から, \(|R_1|=(P_D(k)-P_{D_p}(k))/p\)であり,
\(|Col_{M,D}(k)|=|X/P|=|R_1|+|R_p|=\frac{1}{p}P_{D}(k)+(1-\frac{1}{p})P_{D_p}(k)\)
を得る.
Case 2; 一般の場合
|P|が素数で割り切れる回数に関する帰納法を用いる. まず, 次の性質を仮定していた (これが外せるかどうかは分からない);
\(\ker(G\rightarrow Aut(D))<G\)に対し, ある\(G\)の正規部分群列\(N_0=G>N_1>N_2>\ldots>N_{s-1}>N_s=N\)が存在して, \(N_i/N_{i+1}\)の位数が素数.
\(N_1\)で\(X\)を割った\(X/N_1=:Y\)のサイズは, 帰納法の仮定からある多項式\(Q(t)\)が存在して, \(|X/N_1|=Q(k)\)である.
\(Y\)を\(N_0/N_1=: N\)で割った位数を計算すればいい. Case 1とほとんど同様にして、あるkに依存しない多項式Pを用いて
\(|Y/N|=P(k)\)
と書けることが示せる。非自明なのは、\(Y\)への\(N\)作用の中で安定化群が\(N\)である点全体\(Z\)のサイズがあるkによらない多項式Qを用いてQ(k)とかけることである。
\(N\)の\(N_0\)における代表系\(S\)に対してStep 1と同様に構成したグラフ\(X_S\)には自然に\(N_1\)が作用する。\(X_S\)のk色彩色全体に\(N_1\)の作用の同値関係を入れたものと\(Z\)は1対1対応しており、帰納法の仮定から条件を満たす多項式\(Q(t)\)が存在する。
