代数的組合せ論の問題

方針. $L_G$ のメビウス関数と $G$ の彩色多項式 ${\chi }_G(t)$ の関係を導き、${\chi }_G(t)$ の $t$ の係数として $\mu (\hat{0},\hat{1})$ を求める。

彩色多項式との関係. 正の整数 $t$ をとり、写像 $f:V\to \{1,\dots ,t\}$ 全体を考える。$f$ に対し、両端の値が等しい辺 $\{u,v\}$（$f(u)=f(v)$）だけからなる全域部分グラフの連結成分による分割を $\pi (f)$ とする。各連結成分は $G$ で連結な集合なので $\pi (f)\in L_G$ である。

$\sigma \in L_G$ に対し、$\pi (f)\ge \sigma$ となることは「$f$ が $\sigma$ の各ブロック上で定数」であることと同値である。実際、$f$ が各ブロック上で定数なら、ブロック内の辺はすべて両端の値が等しく、ブロックは連結なので 1 つの連結成分に含まれる。逆に $\pi (f)\ge \sigma$ なら各ブロックは同じ値をとる頂点の連結成分に含まれるので $f$ は定数である。したがって
$$\#\{f:\pi (f)\ge \sigma \}=t^{|\sigma |}(|\sigma |\text{ はブロックの個数})$$
である。$g(\tau )=\#\{f:\pi (f)=\tau \}$ とおくと $t^{|\sigma |}={\sum }_{\tau \ge \sigma }g(\tau )$ なので、メビウスの反転公式（上向きの形）により
$$g(\sigma )=\sum _{\tau \ge \sigma }\mu (\sigma ,\tau )t^{|\tau |}.$$
$g(\hat{0})$ はどの辺の両端も値が異なる $f$、すなわち $t$ 色による正しい彩色の個数 ${\chi }_G(t)$ だから
$${\chi }_G(t)=\sum _{\tau \in L_G}\mu (\hat{0},\tau )t^{|\tau |}.$$
両辺は $t$ の多項式で、無限個の $t$ で一致するので多項式として等しい。ブロックが 1 つの元は $\hat{1}$ だけなので、$\mu (\hat{0},\hat{1})$ は ${\chi }_G(t)$ の $t^1$ の係数である。

彩色多項式の計算. $G$ は三角形 $1\text{-}2\text{-}3$ と $4$ 頂点の閉路 $1\text{-}3\text{-}4\text{-}5$ を辺 $\{1,3\}$ で貼り合わせたものである。辺 $\{1,3\}$ の両端の色の組（異なる 2 色）を固定すると、頂点 $2$ と頂点 $4,5$ の塗り方は独立に決まるので
$${\chi }_G(t)=\frac{{\chi }_{C_3}(t){\chi }_{C_4}(t)}{t(t-1)}.$$
ここで ${\chi }_{C_n}(t)=(t-1{)}^n+(-1{)}^n(t-1)$ より
$${\chi }_{C_3}(t)=t(t-1)(t-2),{\chi }_{C_4}(t)=(t-1{)}^4+(t-1)=(t-1)(t^3-3t^2+3t)=t(t-1)(t^2-3t+3).$$
よって
$${\chi }_G(t)=t(t-1)(t-2)(t^2-3t+3).$$
$t$ の係数は $(t-1)(t-2)(t^2-3t+3)$ の定数項だから
$$(-1)\cdot (-2)\cdot 3=6.$$

（確認: 弦 $\{1,3\}$ について削除・縮約公式を使うと ${\chi }_G(t)={\chi }_{C_5}(t)-t(t-1{)}^2(t-2)=(t-1{)}^5-(t-1)-t(t-1{)}^2(t-2)$ で、$t$ の係数は $5-1-(-2)=6$ となり一致する。また $L_G$ の階数は $4$ なので符号 $(-1{)}^4=+1$ とも整合する。）

したがって $\mu (\hat{0},\hat{1})=6$ である。

連結部分グラフを誘導するブロックからなる分割の束 $L_G$ は $G$ の結合束（bond lattice）で、$G$ の彩色多項式は ${\chi }_G(t)={\sum }_{\pi \in L_G}\mu (\hat{0},\pi )t^{|\pi |}$ と表される（$G$ は連結）。したがって $\mu (\hat{0},\hat{1})$ は ${\chi }_G(t)$ の $t^1$ の係数である。
$G$ は三角形 $\{1,2,3\}$ と 4 サイクル $1\text{-}3\text{-}4\text{-}5$ が辺 $\{1,3\}$ を共有して貼り合わさったもの。よって ${\chi }_G(t)={\chi }_{K_3}(t){\chi }_{C_4}(t)/(t(t-1))$。ここで ${\chi }_{K_3}=t(t-1)(t-2)$、${\chi }_{C_4}=(t-1{)}^4+(t-1)=t(t-1)(t^2-3t+3)$。ゆえに ${\chi }_G(t)=t(t-1)(t-2)(t^2-3t+3)$。
$t^1$ の係数は $(-1)(-2)(3)=6$。検算: $t=2$ で ${\chi }_G(2)=0$（三角形を含むので 2 彩色不可）で整合。係数の符号は $(-1{)}^{|V|-1}=+1$ とも整合し、${\chi }_G(t)=t^5-6t^4+14t^3-15t^2+6t$ の辺の数 6 とも一致する。よって $\mu (\hat{0},\hat{1})=6$。