Kasteleynの定理

同義語:Kasteleyn's theoremKasteleyn theorem

概要

Kasteleynの定理(Kasteleyn's theorem)とは、有限の平面グラフは Pfaffian 向き付けをもつ、すなわち辺を向き付けて作った交代行列の Pfaffian の絶対値が完全マッチングの個数(重み付きなら重み和)に等しくなるようにできるという定理である。各有界面で時計回りの辺の本数を奇数にすればよく、Pfaffian の 2 乗は行列式なので、平面グラフの完全マッチングの数え上げは多項式時間でできる。帰結として $2m\times2n$ の盤のドミノの敷き詰めの個数の積公式が得られ、$8\times8$ では $12988816$ である。平面性は外せず、$K_{3,3}$ はこの向き付けをもたない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Pfaffian, マッチング(グラフ理論), 平面グラフ

Kasteleynの定理(Kasteleyn's theorem)とは、有限の 平面グラフ の辺をうまく向き付けると、その向き付けから作った交代行列の Pfaffian の絶対値が、グラフの完全マッチングの個数に等しくなる、という定理である。Pfaffian の 2 乗は 行列式 なので、平面グラフの完全マッチングの個数は消去法で多項式時間で計算できる。一般のグラフでは、この個数の計算は(二部グラフに限っても)#P 完全である(Val79、Tho06 §2)。平面性が、数え上げを行列式の計算に変える。
最もよく知られた帰結は、$2m\times2n$ の盤を $1\times2$ のドミノで敷き詰める方法の個数の積公式
$$ \prod_{j=1}^{m}\prod_{k=1}^{n}\Bigl(4\cos^2\frac{\pi j}{2m+1}+4\cos^2\frac{\pi k}{2n+1}\Bigr) $$
である。各因子は無理数でも積は整数で、$8\times8$ のチェス盤では $12988816$ 通りになる。この方法は 1961 年の Kasteleyn(Kas61)と Temperley–Fisher(TF61)の仕事にさかのぼる。一般の平面グラフについての定理の形は Kas67 にある(Tho06 §1)。

主張内容この記事で
thm-kas-signPfaffian 向き付けでは $\lvert\mathrm{Pf}\rvert$ が完全マッチングの重み和証明する
thm-kas-main平面グラフは Pfaffian 向き付けをもつ証明する
thm-kas-dominoドミノの敷き詰めの個数の積公式証明する
prop-kas-bip二部グラフでは行列式、$K_{3,3}$ は向き付けをもたない証明する
rem-kas-beyond種数 $g$ の曲面、敷き詰めのエントロピー主張と所在

定義

$G$ を頂点集合 $\{1,\dots,2n\}$ の有限単純グラフとし、各辺 $e$ に正の重み $w_e$ を与える。完全マッチング とは、どの頂点もちょうど 1 本に含まれる辺の集合である。その全体を $\mathcal{M}(G)$ とおき、
$$ Z(G,w):=\sum_{M\in\mathcal{M}(G)}\prod_{e\in M}w_e $$
を 重み和 とよぶ。$w\equiv1$ なら $Z$ は完全マッチングの個数である。

向き付けの行列

$G$ の各辺に向きを与えたものを $G$ の 向き付け $D$ という。交代行列 $A=A(D,w)=(a_{ij})$ を、$D$ に辺 $i\to j$ があれば $a_{ij}=w_{ij}$、$a_{ji}=-w_{ij}$、$i,j$ が隣接しなければ $a_{ij}=0$ と定める。

完全マッチング $M=\{\{p_1,q_1\},\dots,\{p_n,q_n\}\}$ に対し、頂点の列 $(p_1,q_1,\dots,p_n,q_n)$ を $(1,\dots,2n)$ の置換とみた符号を $\operatorname{sgn}$ と書き、
$$ t(M):=\operatorname{sgn}(p_1,q_1,\dots,p_n,q_n)\prod_{k=1}^na_{p_kq_k} $$
とおく。対の中の 2 つを入れ替えると符号と成分が同時に $-1$ 倍になり、対どうしの並べ替えは偶置換なので、$t(M)$ は列の取り方によらない。Pfaffian の定義により $\mathrm{Pf}(A)=\sum_{M\in\mathcal{M}(G)}t(M)$ である(隣接しない対を含むマッチングの項は $0$)。$\lvert t(M)\rvert=\prod_{e\in M}w_e$ なので、問題は項の符号がそろうかどうかである。

中心的な閉路と奇の向き付け

$G$ の閉路 $C$ で、$G$ から $C$ の頂点を除いたグラフ $G\setminus V(C)$ が完全マッチングをもつものを 中心的(central)という。このとき $C$ の長さは偶数である。偶数長の閉路 $C$ が 奇に向き付けられている とは、$C$ を一方向にたどるとき、たどる向きと同じ向きの辺の本数が奇数であることをいう(長さが偶数なので、たどる方向によらない)。すべての中心的な閉路が奇に向き付けられている向き付けを Pfaffian 向き付け という。

主定理

符号がそろう条件

$D$ を $G$ の向き付けとする。$D$ が Pfaffian 向き付けであることと、すべての完全マッチング $M$ の $t(M)$ の符号が同じであることは同値である。このとき
$$ \lvert\mathrm{Pf}(A(D,w))\rvert=Z(G,w),\qquad\det A(D,w)=Z(G,w)^2 $$
である。

2 つのマッチングの対称差

$M,M'\in\mathcal{M}(G)$ とする。$M\cup M'$ の連結成分は、共通の辺と、$M$ の辺と $M'$ の辺が交互に並ぶ偶数長の閉路 $C_1,\dots,C_r$ である。$M$ から $C_i$ 上の辺を除いたものは $G\setminus V(C_i)$ の完全マッチングなので、各 $C_i$ は中心的である。
閉路 $C_i$ の頂点をたどる順に $v_1,\dots,v_{2s}$ と並べ、$\{v_1,v_2\},\{v_3,v_4\},\dots$ が $M$ の辺、$\{v_2,v_3\},\dots,\{v_{2s},v_1\}$ が $M'$ の辺であるようにする。$M$ の頂点の列 $L$ を、各閉路の $v_1,\dots,v_{2s}$ をつなぎ、最後に共通の辺の両端を並べて作る。$M'$ の頂点の列 $L'$ を、$L$ の各閉路の部分を $v_2,\dots,v_{2s},v_1$ に替えて作る。$L$ から $L'$ へは長さ偶数の巡回置換を $r$ 個施すので、$\operatorname{sgn}L\operatorname{sgn}L'=(-1)^r$ である。よって
$$ t(M)t(M')=(-1)^r\prod_{i=1}^r\Bigl(\prod_{l}a_{v_lv_{l+1}}\Bigr)\prod_{\{x,y\}\in M\cap M'}a_{xy}^2 $$
である($l$ は $C_i$ の頂点の番号を巡回的に動く)。$a_{v_lv_{l+1}}$ の符号は、辺がたどる向きと同じなら $+1$、逆なら $-1$ である。$C_i$ でたどる向きと同じ辺の本数を $f_i$ とすると、長さが偶数なので逆向きの本数の偶奇も $f_i$ と同じで、
$$ \operatorname{sign}\bigl(t(M)t(M')\bigr)=\prod_{i=1}^r(-1)^{1+f_i}\qquad(\ast) $$
である。Pfaffian 向き付けならすべての $f_i$ が奇数なので、$t(M)t(M')>0$ である。
逆に、符号がすべて同じとし、$C$ を中心的な閉路とする。$G\setminus V(C)$ の完全マッチングに $C$ の 2 通りの交互の辺の取り方を足すと、$M\cup M'$ の閉路が $C$ だけの $M,M'$ が得られる。$(\ast)$ から $f$ は奇数である。
符号がそろえば $\lvert\mathrm{Pf}(A)\rvert=\sum_M\lvert t(M)\rvert=Z(G,w)$ で、$\det A=\mathrm{Pf}(A)^2$ である(Pfaffian の記事の定理「Pfaffian の平方は行列式」)。$\square$

平面グラフでは次の向き付けを使う。平面に描いた連結なグラフの各面について、面を右手に見ながら境界を 1 周する閉じた歩道を、その面の 境界の歩道 とよぶ。有界な面では、境界が閉路なら時計回りの周回である。各辺はちょうど 2 回たどられ(辺の両側に対応する)、その 2 回の向きは逆である。有界な面 $F$ について、$F$ の境界の歩道のうち辺の向きと一致する回数を $c_F$ とする。

面の条件を満たす向き付け

$G$ を連結な平面グラフとする(平面に描いて固定する)。すべての有界な面 $F$ で $c_F$ が奇数である向き付けが存在する。

外の面に接する辺から帰納する

有界な面の個数 $f$ についての帰納法による。$f=0$ なら $G$ は木で、どの向き付けでもよい。$f\ge1$ とする。隣り合う面を辺を越えてたどれば任意の 2 つの面は結ばれるので、有界な面 $F$ と非有界な面の両方に接する辺 $e$ がある。$e$ の両側の面は異なるので $e$ は橋でなく、$G-e$ は連結で、有界な面は $F$ 以外そのまま残り、その境界の歩道も変わらない。帰納法の仮定で $G-e$ に向き付けを与え、$e$ の向きを $c_F$ が奇数になるように選ぶ。$e$ は $F$ の境界の歩道に 1 回だけ現れるので、これはできる。$\square$

閉路の時計回りの本数

lem-kas-faces の向き付けで、$C$ を $G$ の閉路とし、$c(C)$ を $C$ の辺のうち時計回りの向きのものの本数、$v(C)$ を $C$ の内部の頂点の個数とする。このとき
$$ c(C)\equiv1+v(C)\pmod2 $$
である。

面についての和と Euler の公式

$C$ とその内部からなる部分グラフを $G'$ とする。$G$ は連結なので、内部の頂点から $C$ へ内部を通る道があり、$G'$ は連結である。$G'$ の有界な面は $G$ の $C$ の内部の面で、個数を $f$ とする。$C$ の内部の辺($C$ 上の辺を除く)の本数を $e$、$C$ の長さを $\ell$ とする。Eulerの多面体定理 により $(v(C)+\ell)-(e+\ell)+(f+1)=2$、すなわち $f-e=1-v(C)$ である。
$\sum_Fc_F$($F$ は $C$ の内部の面)を辺ごとに数える。内部の辺は逆向きに 2 回たどられるので、ちょうど 1 回だけ数えられる。$C$ 上の辺は内側の面の歩道で時計回りに 1 回だけたどられるので、時計回りの向きのときだけ数えられる。よって $\sum_Fc_F=e+c(C)$ である。各 $c_F$ は奇数なので $f\equiv e+c(C)$ となり、$c(C)\equiv f-e=1-v(C)\equiv1+v(C)$ を得る。$\square$

Kasteleyn の定理

有限の平面グラフは Pfaffian 向き付けをもつ。したがって、辺の重みが正なら $Z(G,w)=\lvert\mathrm{Pf}(A(D,w))\rvert=\sqrt{\det A(D,w)}$ である。

中心的な閉路の頂点はすべて 1 つの連結成分にあり、その成分から閉路の頂点を除いたグラフも完全マッチングをもつので、成分ごとに向き付ければよい。$G$ を連結とし、lem-kas-faces の向き付けをとる。$C$ を中心的な閉路とする。$G\setminus V(C)$ の完全マッチングの辺は $C$ と交わらないので、$C$ の内部の頂点は内部の頂点どうしで対になり、$v(C)$ は偶数である。lem-kas-parity により時計回りの辺の本数 $c(C)$ は奇数である。これは $C$ が奇に向き付けられていることを意味する。結論の等式は thm-kas-sign である。$\square$

lem-kas-parity から分かるように、内部の頂点が奇数個の閉路は奇に向き付けられない。この向き付けはそれらの閉路を相手にせず、中心的な閉路だけを奇にする。

計算の手順

証明はそのまま算法になる。平面に描き、外の面に接する橋でない辺を順に取り除いて木にし、木の辺を任意に向き付け、取り除いた辺を逆の順に戻しながら、lem-kas-faces のとおりに向きを決める。最後に $\det A$ を消去法で求めて平方根をとる。重みが有理数なら $\det A$ の計算は多項式時間である。

例

正方形:向きを間違えると消える

4-閉路を頂点 $1,2$(上の段)、$3,4$(下の段)で描き、辺を $12,34,13,24$ とする。完全マッチングは $\{12,34\}$ と $\{13,24\}$ の 2 つで、$\mathrm{Pf}(A)=a_{12}a_{34}-a_{13}a_{24}+a_{14}a_{23}$ の第 3 項は $0$ である。

  • $1\to2$、$3\to4$、$1\to3$、$2\to4$ と向けると、$\mathrm{Pf}(A)=1-1=0$ である。時計回りの本数は $c_F=2$ で偶数である。
  • $3\to4$ を $4\to3$ に替えると、$\mathrm{Pf}(A)=-1-1=-2$ で、絶対値が個数に一致する。$c_F=3$ である。
二部でない平面グラフ $K_4$

$K_4$ を、外周の三角形 $1,2,3$(時計回りの順)と中心の頂点 $4$ で描く。$1\to2$、$2\to3$、$1\to3$、$1\to4$、$4\to2$、$3\to4$ と向けると、面 $124$、$234$、$314$ の $c_F$ はそれぞれ $1$、$3$、$1$ で奇数である。外周は内部の頂点が 1 個なので、lem-kas-parity のとおり $c=2$ である。このとき
$$ \mathrm{Pf}(A)=a_{12}a_{34}-a_{13}a_{24}+a_{14}a_{23}=1+1+1=3 $$
で、$K_4$ の完全マッチングの個数と一致する。

ドミノの敷き詰め

$M\times N$ の盤のマス $(a,j)$($1\le a\le M$、$1\le j\le N$)を頂点とし、辺を共有するマスを結んだグラフを $G_{M,N}$ とする。ドミノの敷き詰めは $G_{M,N}$ の完全マッチングと 1 対 1 に対応する。

敷き詰めの個数の積公式

$m,n\ge1$ について、$2m\times2n$ の盤のドミノの敷き詰めの個数は
$$ \prod_{j=1}^{m}\prod_{k=1}^{n}\Bigl(4\cos^2\frac{\pi j}{2m+1}+4\cos^2\frac{\pi k}{2n+1}\Bigr) $$
である。

行列の 2 乗が対角化できる

$M=2m$、$N=2n$ とする。行番号 $a$ が下へ増え、列番号 $j$ が右へ増えるように描く。$a$ が偶数の行の横の辺は右向き、奇数の行の横の辺は左向き、縦の辺はすべて下向きとする。
向き付けの確認. 有界な面は単位正方形で、左上の頂点を $(a,j)$ とする。時計回りに $(a,j)\to(a,j+1)\to(a+1,j+1)\to(a+1,j)\to(a,j)$ とたどると、右の縦の辺は一致し、左の縦の辺は一致しない。上下の横の辺は、$a$ が偶数なら両方一致し、$a$ が奇数なら両方一致しない。よって $c_F$ は $3$ か $1$ で奇数である。thm-kas-main の証明により、敷き詰めの個数は $\lvert\mathrm{Pf}(A)\rvert$ に等しい。
行列の形. $B_L$ を $(B_L)_{l,l+1}=1$、$(B_L)_{l+1,l}=-1$、他は $0$ の $L$ 次交代行列、$E$ を $M$ 次の対角行列 $\operatorname{diag}((-1)^a)$ とする。頂点を辞書式に並べると
$$ A=E\otimes B_N+B_M\otimes I_N $$
である。$B_M$ は隣り合う添字だけを結ぶので $EB_M=-B_ME$ で、$E^2=I_M$ である。よって交差項が消えて
$$ A^2=I_M\otimes B_N^2+B_M^2\otimes I_N $$
となる。
固有値. $U_L:=\operatorname{diag}(\sqrt{-1}^{\,l})$ とおくと $U_L^{-1}B_LU_L=\sqrt{-1}\,P_L$ である。ここで $P_L$ は 道グラフ の隣接行列で、固有値は $2\cos\frac{\pi k}{L+1}$($k=1,\dots,L$)、固有ベクトルは $(\sin\frac{\pi lk}{L+1})_l$ である(道グラフの記事の固有値の定理)。よって $B_L^2$ の固有値は $-4\cos^2\frac{\pi k}{L+1}$ である。$A^2$ の 2 つの項は可換なので、
$$ \det(A^2)=\prod_{j=1}^{M}\prod_{k=1}^{N}\bigl(-\lambda_{jk}\bigr),\qquad\lambda_{jk}:=4\cos^2\frac{\pi j}{M+1}+4\cos^2\frac{\pi k}{N+1} $$
である。$MN$ は偶数なので符号は消える。$\det(A^2)=(\det A)^2=\mathrm{Pf}(A)^4$ である。
4 乗根. $\lambda_{jk}=\lambda_{M+1-j,k}=\lambda_{j,N+1-k}$ で、$M,N$ は偶数なので $j\mapsto M+1-j$、$k\mapsto N+1-k$ に固定点はない。よって
$$ \mathrm{Pf}(A)^4=\Bigl(\prod_{j=1}^m\prod_{k=1}^n\lambda_{jk}\Bigr)^4 $$
であり、$\lambda_{jk}>0$ なので 4 乗根をとって結論を得る。$\square$

盤積公式の計算個数
$2\times2$$4\cos^2\frac\pi3+4\cos^2\frac\pi3=1+1$$2$
$2\times4$$(1+\phi^2)(1+\phi^{-2})$($\phi=\frac{1+\sqrt5}2$、$4\cos^2\frac\pi5=\phi^2$、$4\cos^2\frac{2\pi}5=\phi^{-2}$)$5$
$4\times4$$(2\phi^2)\,(\phi^2+\phi^{-2})^2\,(2\phi^{-2})$$36$
$6\times6$$6728$
$8\times8$$12988816$

$2\times2n$ の盤の値は Fibonacci数 $F_{2n+1}$ である($2\times4$ で $F_5=5$)。$8\times8$ までの値は、積公式とは別に、マス目を順に埋める数え上げでも確かめた。

奇数の辺をもつ盤

証明の $A^2$ の計算は $MN$ が偶数なら同じである。$M=2m$、$N=2n+1$ では、$k=n+1$ で $\cos\frac{\pi k}{N+1}=0$ となり、固定点の因子 $\prod_{j=1}^m4\cos^2\frac{\pi j}{2m+1}$ が現れる。$P_{2m}$ の行列式の絶対値が $1$(完全マッチングがただ 1 つ)で、その固有値の積が $\pm\prod_{j=1}^m4\cos^2\frac{\pi j}{2m+1}$ なので、この因子は $1$ である。よって個数は $\prod_{j\le m}\prod_{k\le n}\lambda_{jk}$ と同じ形になる。たとえば $2\times3$ では $4\cos^2\frac\pi3+4\cos^2\frac\pi4=3$ である。$M,N$ がともに奇数なら頂点数が奇数で、完全マッチングはない。

二部グラフと $K_{3,3}$

二部グラフでは行列式になる

$G$ を、頂点が $x_1,\dots,x_n$ と $y_1,\dots,y_n$ に分かれた二部グラフとし、$D$ を向き付けとする。$K_{il}:=a_{x_iy_l}$ で $n$ 次正方行列 $K$ を定める。

  1. $\lvert\mathrm{Pf}(A)\rvert=\lvert\det K\rvert$ である。$D$ が Pfaffian 向き付けなら、$\lvert\det K\rvert$ は重みの行列 $(w_{x_iy_l})$ のパーマネントに等しい。
  2. $K_{3,3}$ は Pfaffian 向き付けをもたない。

1:頂点を $x_1,\dots,x_n,y_1,\dots,y_n$ の順に並べると $A=\begin{pmatrix}0&K\\-K^{\mathsf T}&0\end{pmatrix}$ で、Pfaffian の記事の例「非対角ブロックの交代行列」により $\mathrm{Pf}(A)=\pm\det K$ である。パーマネントは完全マッチングの重み和 $Z$ そのものなので、thm-kas-sign から従う。
2:$K_{3,3}$ の完全マッチングは $3!=6$ 個である。Pfaffian 向き付けがあれば、成分が $\pm1$ の $3$ 次行列 $K$ で $\lvert\det K\rvert=6$ となる。しかし Hadamardの不等式(行列式) により $\lvert\det K\rvert\le3^{3/2}< 6$ である。$\square$

$K_{3,3}$ は平面的でないので、これは thm-kas-main の平面性が外せないことを示す。成分が $\pm1$ の $3$ 次行列の行列式の絶対値の最大は実際には $4$ である($2^9$ 通りの全数で確かめた)。1 は、パーマネントを符号の付け替えで行列式に直す Pólya の問題(Tho06 §3)の、平面グラフでの答えでもある。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなるもの
平面性$K_{3,3}$(prop-kas-bip)thm-kas-main の結論(向き付けの存在)
面の奇数性ex-kas-square の 1 つ目:$\mathrm{Pf}=0$$\lvert\mathrm{Pf}\rvert=Z$
二部性ex-kas-k4:頂点の二分がなく $K$ が作れないprop-kas-bip の行列式の形(Pfaffian の形は成り立つ)

平面性は十分条件であって必要条件ではない。Heawood グラフは Pfaffian 向き付けをもつ(Tho06 §4)が、頂点 14、辺 21、内周 6 なので、Euler の公式の評価 $E\le\frac32(V-2)=18$ に反し平面的でない。

平面の外と大きな盤

次はこの記事では証明しない。

  1. 二部グラフが Pfaffian 向き付けをもつのは、$K_{3,3}$ を matching minor(中心的な部分グラフから、次数 $2$ の頂点の 2 辺の縮約を繰り返して得られるグラフ)としてもたないときに限る(Little の定理、Tho06 Theorem 4.1)。
  2. 種数 $g$ の向き付け可能な曲面に埋め込めるグラフでは、$4^g$ 個の向き付けの Pfaffian の線形結合で個数が表せる(Tho06 Theorem 7.3)。Kasteleyn が指摘し、Galluccio–Loebl と Tesler が証明した。
  3. $M,N\to\infty$ で $\frac1{MN}\log(\text{敷き詰めの個数})\to\mathcal{C}/\pi\approx0.29156$ である。ここで $\mathcal{C}=1-\frac1{3^2}+\frac1{5^2}-\cdots$ は Catalan の定数である(Ken09 §4.1)。thm-kas-domino で $M=N=1600$ とすると $0.29137$ である。
  4. 同じ方法は 2 次元の Isingモデル の分配関数の計算にも使える(Tho06 §2)。

関連項目

参考文献

[1]
Robin Thomas, A survey of Pfaffian orientations of graphs, Proceedings of the International Congress of Mathematicians, Madrid 2006, 2006, 963–984(§1、§2、§3、§4、Theorem 4.1、Theorem 7.3)
[2]
Richard Kenyon, Lectures on dimers, Statistical Mechanics, IAS/Park City Mathematics Series 16, American Mathematical Society (2009), 191–230。arXiv:0910.3129, 2009, arXiv 版 v1 の §4.1(pp. 22–23)
[3]
P. W. Kasteleyn, The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice, Physica, 1961, 1209–1225
[4]
P. W. Kasteleyn, Graph theory and crystal physics, Graph Theory and Theoretical Physics(F. Harary 編、Academic Press), 1967, 43–110
[5]
H. N. V. Temperley, M. E. Fisher, Dimer problem in statistical mechanics—an exact result, Philosophical Magazine, 1961, 1061–1063
[6]
L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science, 1979, 189–201

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する