代数的組合せ論の問題

$L_G$ の要素を決める. $\{1,2,3,4\}$ の集合分割は全部で $15$ 個ある。ブロックが誘導する部分グラフが連結でないのは、辺をもたない 2 元集合 $\{1,4\}$ だけである（3 元集合 $\{1,2,4\}$ は辺 $12,24$ で、$\{1,3,4\}$ は辺 $13,34$ で連結。$\{1,2,3\},\{2,3,4\}$ は三角形。全体 $\{1,2,3,4\}$ も連結）。したがって $\{1,4\}$ をブロックにもつ $\{14\}\{2\}\{3\}$ と $\{14\}\{23\}$ の 2 個を除いた $13$ 個が $L_G$ の要素である。以下、1 元ブロックは省略して書く（例: $\{12\}$ は $\{1,2\}\{3\}\{4\}$）。

$\mu (\hat{0},x)$ を下から順に計算する.

• $\mu (\hat{0},\hat{0})=1$。
• 2 元ブロックを 1 つもつもの $\{12\},\{13\},\{23\},\{24\},\{34\}$（5 個）: 下にあるのは $\hat{0}$ だけなので、それぞれ $\mu =-1$。
• 3 元ブロックをもつもの:
• $\{123\}$: その下（自身を除く）は $\hat{0}$ と $\{12\},\{13\},\{23\}$。$\mu =-(1-3)=2$。
• $\{124\}$: 下は $\hat{0}$ と $\{12\},\{24\}$（$\{14\}$ は $L_G$ にない）。$\mu =-(1-2)=1$。
• $\{134\}$: 下は $\hat{0}$ と $\{13\},\{34\}$。$\mu =1$。
• $\{234\}$: 下は $\hat{0}$ と $\{23\},\{24\},\{34\}$。$\mu =2$。
• 2 元ブロックを 2 つもつもの:
• $\{12\}\{34\}$: 下は $\hat{0},\{12\},\{34\}$。$\mu =-(1-2)=1$。
• $\{13\}\{24\}$: 下は $\hat{0},\{13\},\{24\}$。$\mu =1$。

$\mu (\hat{0},\hat{1})$. $\hat{1}$ より真に小さいのは上の 12 個すべてなので
$$\mu (\hat{0},\hat{1})=-(1+5\cdot (-1)+(2+1+1+2)+(1+1))=-(1-5+6+2)=-4.$$

検算. $L_G$ はグラフ $G$ の閉路マトロイドのフラットの束（ボンド束）であり、連結グラフ $G$ の彩色多項式は ${\chi }_G(q)={\sum }_{\pi \in L_G}\mu (\hat{0},\pi )q^{|\pi |}$（$|\pi |$ はブロック数）と書ける。$\hat{1}$ はブロック数 1 なので、$\mu (\hat{0},\hat{1})$ は ${\chi }_G(q)$ の $q$ の係数である。$G$ は三角形 $123$ に頂点 $4$ を $2,3$ の両方に隣接させたものなので ${\chi }_G(q)=q(q-1)(q-2)\cdot (q-2)=q^4-5q^3+8q^2-4q$ で、$q$ の係数は $-4$ となり一致する。

よって ${\mu }_{L_G}(\hat{0},\hat{1})=-4$。

$L_G$ は $G$ の結合束で、連結グラフ $G$ について ${\chi }_G(t)={\sum }_{\pi \in L_G}\mu (\hat{0},\pi )t^{|\pi |}$ が成り立つ。よって $\mu (\hat{0},\hat{1})$ は彩色多項式の $t^1$ の係数。
$G$ は辺 $23$ を共有する 2 つの三角形 $\{1,2,3\}$, $\{2,3,4\}$ の貼り合わせなので ${\chi }_G(t)=\frac{t(t-1)(t-2)\cdot t(t-1)(t-2)}{t(t-1)}=t(t-1)(t-2{)}^2$。
$t^1$ の係数は $(-1)\cdot (-2{)}^2=-4$。符号は $(-1{)}^{|V|-1}=-1$ と整合。
検算（直接計算）: 連結ブロックのみの分割を数える。ランク 0: $\hat{0}$、$\mu =1$。ランク 1（1 辺を併合）: 5 個、各 $\mu =-1$。ランク 2: 3 点ブロック＋単点は、三角形 123 と 234 の 2 個（各 $\mu =2$、区間が 3 本の辺のうち 3 つの原子を含む）、2+2 分割は $\{12\}\{34\}$ と $\{13\}\{24\}$（$\{14\}\{23\}$ は辺 14 がなく不可）で各 $\mu =1$、原子 3 個でなく他は連結でない；3 点ブロック $\{1,2,4\}$（辺 12,24 で連結）と $\{1,3,4\}$（辺 13,34 で連結）も連結で各 $\mu =1$。ランク 2 の $\mu$ の和は $2+2+1+1+1+1=8$、全体で $\mu (\hat{0},\hat{1})=-(1-5+8)=-4$。よって $-4$。