閉路グラフのマッチング多項式〜チェビシェフ多項式の話２

第一種チェビシェフ多項式は， $\cos n\theta=T_n(\cos \theta)$ により定義される多項式 $T_n(x)\, n=0,1,2,\ldots$ であり，
漸化式
$T_0(x)=1,$
$T_1(x)=x,$
$T_{n+1}(x)=2xT_n(x)-T_{n-1}(x),\quad(n\geq 1).$
により定義することもできます．
第一種チェビシェフ多項式についてはこのブログでも以前話題に上げました．
iwalion.hatenablog.com

第一種チェビシェフ多項式は「閉路グラフのマッチング」と呼ばれる組合せ論的オブジェクトの母関数としても定義することができます．
この記事では，閉路グラフのマッチングを定義し，その母関数が上で定義したチェビシェフ多項式に一致することを述べます．

この話題は，Viennot先生による組合せ論のYoutube講義でも紹介されています．
youtu.be

グラフのマッチング

単純無向グラフ $G=(V,E)$ が与えられているとします．枝集合 $E$ の部分集合 $M\subseteq E$ が，「 $M$ に含まれるどの二つの枝 $e_1,e_2\in M$ も同じ端点を共有しない」という条件を満たすとき， $M$ はグラフ $G$ のマッチングであるといいます．
グラフ $G$ のマッチングの集合を $\mathcal{M}(G)$ と表します．

節点集合 $V_n\triangleq\{1,.2,\ldots,n\}$ と，枝集合 $E_n\triangleq\left\{\{1,2\},\{2,3\},\ldots,\{n,1\}\right\}$
からなる単純無向グラフ $\gamma_n\triangleq(V_n,E_n)$ を長さ $n$ の閉路グラフといいます．

下図の左側は，長さ $5$ の閉路グラフ $\gamma_5$ で，図の右側はそのマッチングの集合 $\mathcal{M}(\gamma_5)$ です．

以下の定理により，長さ $n+1$ の閉路グラフのマッチングの集合は，長さ $n$ および長さ $n-1$ の閉路グラフのマッチングの集合から作ることができます．

定理
次の全単射 $f$ が存在する．
$f\colon\mathcal{M}(\gamma_{n})\sqcup \mathcal{M}(\gamma_{n-1})\to \mathcal{M}(\gamma_{n+1})$

例を使った説明
長さ $3$ と $4$ の閉路グラフのマッチングから長さ $5$ の閉路グラフのマッチングを作ってみせます．
基本的な考え方は，

長さ $n-1$ の閉路のマッチングには節点二つとそれを結ぶ枝一つを突っ込み
長さ $n$ の閉路のマッチングには，節点を一つ突っ込む

ことにより，長さ $n+1$ の閉路のマッチングを作ることです．但し，単純に突っ込めない場合に多少局所的な操作を行うことが必要になります．

まずマッチング $M\in\mathcal{M}(\gamma_3)$ に枝を一本突っ込んで $\mathcal{M}(\gamma_5)$ を作ります．

閉路グラフ $\gamma_3$ の節点 $1$ と節点 $3$ の”左側”に新しい枝とその両端点となる節点二つを置きます．（図の上側）
$\{1,3\}\notin M$ の場合，それがそのまま $\gamma_5$ のマッチングになります．
$\{1,3\}\in M$ の場合，節点 $1,3$ と新しい二つの節点の間で枝を付け替えることで， $\gamma_5$ のマッチングが得られます．（図の最右列）
この操作は可逆です．

次にマッチング $M\in\mathcal{M}(\gamma_4)$ に節点を一つ入れて $\mathcal{M}(\gamma_5)$ に含まれるマッチングを作ります．

閉路グラフ $\gamma_4$ の節点 $1$ と節点 $4$ の”左側”に節点を置きます．
$\{1,4\}\notin M$ の場合，それがそのまま $\gamma_5$ のマッチングになります．
$\{1,4\}\in M$ の場合，枝 $\{1,4\}$ を取り除いて，代わりに $4$ と新しい節点の間に枝を置くことで $\gamma_5$ のマッチングが得られます．
この操作も可逆です．

以上で，全単射 $\mathcal{M}(\gamma_{3})\sqcup \mathcal{M}(\gamma_{4})\to \mathcal{M}(\gamma_{5})$ が得られたことになります．

証明の概略
上で述べた「局所的な操作」は，いずれも操作する部分以外には影響を与えないので，上で述べた方法で一般に写像
$f\colon\mathcal{M}(\gamma_{n-1})\sqcup \mathcal{M}(\gamma_{n})\to \mathcal{M}(\gamma_{n+1})$
が構成できます．
逆写像 $g\colon\mathcal{M}(\gamma_{n+1})\to\mathcal{M}(\gamma_{n-1})\sqcup \mathcal{M}(\gamma_{n})$
を作るには， $M\in\mathcal{M}(\gamma_{n+1})$ において

節点 $n+1$ がマッチングに含まれない
$\{n,n+1\},\{1,2\}\in M$
$\{n,n+1\}\in M,\{1,2\}\notin M$
$\{n+1,1\}\in M$

の四通りに場合分けして節点（と枝）を取り除く操作を考えれば，逆写像ができます．

マッチングの母関数（マッチング多項式）

上で述べた全単射の存在から，長さ $n$ の閉路グラフのマッチングの個数に関して漸化式
$\#\mathcal{M}(\gamma_{n+1})=\#\mathcal{M}(\gamma_{n})+\#\mathcal{M}(\gamma_{n-1})$
が成り立つことが分かります．
この漸化式と $\#\mathcal{M}(\gamma_3)=4, \#\mathcal{M}(\gamma_4)=7$ から定まる数列はリュカ数列と呼ばれる数列の一つです．
A000032 - OEIS

グラフ $G$ のマッチング $M$ の重み $w\colon\mathcal{M}(G)\to \mathbb{R}[x$ ]を，
$w(M)\triangleq(-1)^{|M|}x^{マッチングに含まれない節点の個数}$
と定めます．グラフ $G$ に対して定まる多項式
$\displaystyle C_{G}(x)\triangleq\sum_{M\in\mathcal{M}(G)}w(M)$
を，グラフ $G$ のマッチング多項式といいます．

例えば以下の通り，長さ $4$ の閉路グラフ $\gamma_4$ のマッチング多項式は $x^4-4x^2+2$ です．

上で考えた全単射によれば， $\mathcal{M}(\gamma_{n+1})$ のマッチングはすべて， $\mathcal{M}(\gamma_{n})$ のマッチングにマッチしていない節点を一つ足すか， $\mathcal{M}(\gamma_{n-1})$ のマッチングにマッチしている枝を一つ足すことによって得られます．

これは，マッチング多項式でいうと， $\gamma_{n+1}$ のマッチング多項式の各和因子は， $\gamma_{n}$ のマッチング多項式の和因子に $x$ をかけるか， $\gamma_{n-1}$ のマッチング多項式の和因子に $-1$ をかけるかして得ることができるということです．
つまり，次の式が成立します．

定理
閉路グラフ $\gamma_n$ のマッチング多項式は次の漸化式を満たす
$C_{\gamma_{n+1}}(x)=xC_{\gamma_n}(x)-C_{\gamma_{n-1}}(x)$

特に，変数 $x$ を $2x$ に変数変換すれば，この漸化式は第一種チェビシェフ多項式 $T_n(x)$ が満たす漸化式と一致します．

マッチング多項式と第一種チェビシェフ多項式の一致

計算してみると $n=3,4$ のときに
$T_3(x)=\displaystyle\frac{1}{2}C_{\gamma_3}(2x),\quad T_4(x)=\frac{1}{2}C_{\gamma_4}(2x)$
が成立します．
よって上で示した漸化式から，全ての $n\geq 3$ において，閉路のマッチング多項式 $C_{\gamma_n}(x)$ と第一種チェビシェフ多項式 $T_n(x)$ の間に
$\displaystyle T_n(x)=\frac{1}{2}C_{\gamma_n}(2x)$
が成立します．