ボンド束と彩色多項式

グラフ $G$ の連結分割の束 $L_{G}$ について、メビウス反転から $P_{G} (k) = \sum_{π \in L_{G}} μ (0^, π) k^{∣ π ∣}$ を導き、 $μ (0^, 1^)$ を彩色多項式の $k$ の 1 次の係数として求められる

前提

メビウス反転公式と直積の積公式（大学院数学代数的組合せ論）
彩色多項式（大学数学離散数学・組合せ論）

この技能までの道筋（12 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

半順序集合のメビウス関数（大学院数学代数的組合せ論）
メビウス反転公式と直積の積公式（大学院数学代数的組合せ論）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）
2 部グラフと奇閉路（大学数学グラフ理論）
最大独立集合と最小頂点被覆（大学数学グラフ理論）
頂点彩色と彩色数（大学数学グラフ理論）
彩色多項式（大学数学離散数学・組合せ論）

説明

グラフ $G = (V, E)$ の頂点集合 $V$ の集合分割のうち、各ブロックが $G$ の連結な誘導部分グラフになっているもの全体を細分の順序で並べたものを、ボンド束（連結分割の束） $L_{G}$ といいます。この技能では、メビウス反転によって彩色多項式が $P_{G} (k) = \sum_{π \in L_{G}} μ (0^, π) k^{∣ π ∣}$ （ $∣ π ∣$ はブロック数）と書けることを導きます。その帰結として、連結グラフ $G$ では $L_{G}$ の最小元から最大元までのメビウス関数 $μ (0^, 1^)$ が「 $P_{G} (k)$ の $k$ の 1 次の係数」に等しくなり、束を書き出さずに彩色多項式の計算だけで $μ (0^, 1^)$ が求まります。

なぜそうしてよいのか

$L_{G}$ の順序は「 $σ \leq τ$ $⟺$ $σ$ の各ブロックが $τ$ のあるブロックに含まれる」です。最小元 $0^$ はすべての頂点がばらばらの分割、 $G$ が連結なら最大元 $1^$ は $V$ 全体の 1 ブロックです。 $k$ 色を自由に割り当てる写像 $c : V \to {1, \dots, k}$ （隣接頂点が同色でもよい）全 $k^{∣ V ∣}$ 個を考え、各 $c$ に対して「両端が同じ色の辺だけを残したグラフの連結成分」による分割 $π (c)$ を対応させます。各ブロックは連結なので $π (c) \in L_{G}$ です。

$f (σ) = # {c : π (c) = σ}$ 、 $g (τ) = # {c : c は τ の各ブロック上で一定}$ とおきます。 $τ$ の各ブロックは連結なので、 $c$ がその上で一定なら、ブロック内の辺はすべて同色の辺として残り、ブロック全体が $π (c)$ の 1 つのブロックに入ります。つまり $π (c) \geq τ$ です。逆に $π (c) \geq τ$ なら、 $τ$ の各ブロックは同色の辺でつながった 1 つの成分に含まれるので、その上で $c$ は一定です。よって $g (τ) = \sum_{σ \geq τ} f (σ)$ で、ブロックごとに 1 色を選ぶので $g (τ) = k^{∣ τ ∣}$ です。また $π (c) = 0^$ は「同色の辺が 1 本もない」、つまり $c$ が正しい彩色であることなので $f (0^) = P_{G} (k)$ です。

メビウス反転公式を上向きに使う形（順序を逆にした半順序集合に前提の公式を適用したもの） $f (τ) = \sum_{σ \geq τ} μ (τ, σ) g (σ)$ を $τ = 0^$ に使うと
$P_{G} (k) = π \in L_{G} \sum μ (0^, π) k^{∣ π ∣}$
が得られます。両辺とも $k$ の多項式で、すべての正の整数 $k$ （無限個）で一致するので、係数ごとに等しくなります。 $G$ が連結なら $∣ π ∣ = 1$ となる $π \in L_{G}$ は $1^$ だけなので、 $k^{1}$ の係数を比べて $μ (0^, 1^) = [k^{1}] P_{G} (k)$ です（ $G$ が連結でなければ、どの $π \in L_{G}$ もブロックが連結成分の中に収まるので $∣ π ∣ \geq c$ （ $c$ は連結成分の個数 $\geq 2$ ）となり、 $k^{1}$ の係数は $0$ で、この読み取りは使えません）。

手順

$G$ が連結であることを確かめる（ $L_{G}$ の最大元 $1^$ が $V$ 全体の 1 ブロックになる条件）
削除縮約公式や基本形（木・閉路・完全グラフ）、頂点を順に塗る積の法則で $P_{G} (k)$ を求める。できれば別の方法（削除縮約と積の法則など）でも求めて一致を確かめる
$P_{G} (k)$ を展開して（または因数分解された形から） $k$ の 1 次の係数を取り出す。展開した場合は、辺が 1 本以上あれば $P_{G} (1) = 0$ （係数の和が $0$ ）となることで計算を検算できる
$μ_{L_{G}} (0^, 1^) = [k^{1}] P_{G} (k)$ とする

例題

完全グラフ $K_{4}$ から辺を 1 本取り除いたグラフ $G$ （頂点 $1, 2, 3, 4$ 、辺 $12, 13, 23, 24, 34$ ）の連結分割の束 $L_{G}$ について、メビウス関数の値 $μ (0^, 1^)$ を求めよ。ただし $0^$ は最小元、 $1^$ は最大元とする。

例題の解答

手順 1: $G$ は連結なので、 $L_{G}$ の最大元 $1^$ は ${1, 2, 3, 4}$ の 1 ブロックの分割である。

手順 2: 頂点を $2, 3, 1, 4$ の順に塗る。 $2$ は $k$ 通り、 $3$ は $2$ と隣接するので $k - 1$ 通り、 $1$ は $2, 3$ の両方と隣接するので $k - 2$ 通り、 $4$ も $2, 3$ の両方と隣接し $1$ とは隣接しないので $k - 2$ 通り。積の法則より
$P_{G} (k) = k (k - 1) (k - 2)^{2} .$
別の方法で確かめる: $K_{4}$ で辺 $14$ に削除縮約公式を使うと $P_{K_{4}} = P_{G} - P_{K_{4} /14}$ で、 $K_{4} /14$ （ $1, 4$ を同一視し重複辺をまとめたもの）は $K_{3}$ なので
$P_{G} = P_{K_{4}} + P_{K_{3}} = k (k - 1) (k - 2) (k - 3) + k (k - 1) (k - 2) = k (k - 1) (k - 2)^{2}$
と一致する。

手順 3: $k$ の 1 次の係数は、 $k$ 以外の因子の定数項の積なので $(- 1) \cdot (- 2)^{2} = - 4$ 。展開すると $P_{G} (k) = k^{4} - 5 k^{3} + 8 k^{2} - 4 k$ で、係数の和 $1 - 5 + 8 - 4 = 0$ が $P_{G} (1) = 0$ と合っている。

手順 4: よって $μ (0^, 1^) = - 4$ 。

答え: $- 4$

よくある誤り

$L_{G}$ を集合分割の束 $Π_{n}$ 全体と混同し、 $μ (0^, 1^) = (- 1)^{n - 1} (n - 1)!$ としてしまう誤り。正しくは $L_{G}$ はブロックが連結な分割だけからなり、 $L_{G} = Π_{n}$ となるのは $G = K_{n}$ のときだけ（隣接しない 2 頂点 $u, v$ があれば ${u, v}$ は連結なブロックにならない）。上の例では $(- 1)^{3} \cdot 3! = - 6$ ではなく $- 4$
$k$ の 1 次の係数ではなく定数項や最高次の係数を読んでしまう誤り。 $P_{G} (k)$ の定数項は $P_{G} (0) = 0$ なので常に $0$ 、最高次は $k^{∣ V ∣}$ で係数 $1$ なので、正しくは $P_{G} (k) = k^{4} - 5 k^{3} + 8 k^{2} - 4 k$ の $k$ の係数 $- 4$ を読む
閉路 $C_{n}$ の彩色多項式 $(k - 1)^{n} + (- 1)^{n} (k - 1)$ から 1 次の係数を取るとき、第 2 項を落として $n (- 1)^{n - 1}$ としてしまう誤り。正しくは第 2 項からも $(- 1)^{n}$ が加わり、 $[k^{1}] P_{C_{n}} = (- 1)^{n - 1} n + (- 1)^{n} = (- 1)^{n - 1} (n - 1)$ （例: $C_{4}$ で $- 3$ ）
非連結なグラフにもそのまま使い、 $μ (0^, 1^) = [k^{1}] P_{G} (k) = 0$ としてしまう誤り。正しくは非連結なら $L_{G}$ の最大元は連結成分による分割で $∣ 1^∣ = c \geq 2$ となり、 $∣ π ∣ = c$ の元は $1^$ だけなので、 $μ (0^, 1^)$ は $k^{c}$ の係数（ $P_{G}$ は各成分の彩色多項式の積なので、各成分の 1 次の係数の積）として読む

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
頂点集合 $V = {1, 2, 3, 4, 5}$ 、辺集合
$E = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 1}}$
の単純グラフ $G$ （長さ $5$ の閉路 $C_{5}$ ）を考える。 $V$ の集合分割のうち、各ブロックが $G$ の誘導部分グラフとして連結であるもの全体を $L_{G}$ とし（ボンド束）、細分による順序（ $σ \leq τ ⟺ σ$ の各ブロックが $τ$ のあるブロックに含まれる）を入れる。 $L_{G}$ の最小元（すべて 1 元ブロック）を $0^$ 、最大元（ブロックが $V$ だけ）を $1^$ とし、 $μ$ を $L_{G}$ のメビウス関数とする。
$μ (0^, 1^)$ の値を求めよ。

ボンド束と彩色多項式

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題