文献あり

無限Hedetniemiの予想の反例

203

グラフ

グラフとは組 $G = (V, E)$ であって， $V$ は集合， $E$ は $[V]^{2} = {{u, v} : u, v \in V}$ の部分集合となるもののことを言う．

テンソル積

二つのグラフ $G_{0}, G_{1}$ のテンソル積 $G_{0} \otimes G_{1}$ とは $(V_{0} \times V_{1}, E_{0} ⋆ E_{1})$ のことで， $V_{0} \times V_{1}$ は通常のデカルト積， $E_{0} ⋆ E_{1}$ は次で定められる集合である：
$E_{0} ⋆ E_{1} = {{(a, b), (c, d)} : a E_{0} c \land b E_{1} d} .$

彩色数

グラフ $G = (V, E)$ の $k$ 彩色とは写像 $c : V \to {0, 1, \dots, k - 1}$ のことを言う．
$k$ 彩色であって，隣り合う頂点同士の色が異なるもの，すなわち，任意の $u, v \in V$ で $u E v$ なものについて $c (u) \neq c (v)$ を満たすものことを良い $k$ 彩色という．

グラフ $G = (V, E)$ の彩色数 $χ (G)$ とは $G$ の良い $k$ 彩色が存在するような $k$ の最小値である．

次がHedetniemiが1966年に立てた予想である．

Hedetniemiの予想

任意の有限グラフ $G_{0}, G_{1}$ について等式
$χ (G_{0} \otimes G_{1}) = min {χ (G_{0}), χ (G_{1})}$
が成り立つ．

ここでこの等式の片側の不等号
$χ (G_{0} \otimes G_{1}) \leq min {χ (G_{0}), χ (G_{1})}$
は明らかなことに注意しよう．
実際， $c$ が $G_{0}$ の良い $k$ 彩色なら $G_{0} \otimes G_{1}$ の彩色を「第1座標だけ見て $c$ を使って色を決める」というように定めればこれは $G_{0} \otimes G_{1}$ の良い $k$ 彩色である．よって $χ (G_{0} \otimes G_{1}) \leq χ (G_{0})$ であり， $G_{1}$ に対しても同じことが言える．

次が2019年 (!)に示された：

Shitov

Hedetniemiの予想は偽である．つまり，ある有限グラフ $G_{0}, G_{1}$ について不等式
$χ (G_{0} \otimes G_{1}) < min {χ (G_{0}), χ (G_{1})}$
が成り立つ．

本稿では，この結果ではなく，無限版Hedetniemiの予想の反例について解説する．

無限色の彩色や彩色数も色の数が有限のときと同様に定められる．

次はHajnalによって1984年に証明された定理である．

Hajnal

任意の無限基数 $κ$ について，グラフ $G_{0}, G_{1}$ が存在して， $χ (G_{0}) = χ (G_{1}) = κ^{+}$ だが $χ (G_{0} \otimes G_{1}) = κ$ .

無限のときの問題が有限のときの問題よりずっと先に解かれているのも面白いところである．

早速Hajnalの定理の証明に入ろう．

$κ$ を無限基数とする． $A \subseteq κ^{+}$ に対して
$V_{A} = {f : f は単射な関数で， dom (f) \in A かつ ran (f) \subseteq κ}$
$V_{A}$ 上の順序を $f < g ⟺ f ⊊ g$ (つまり $f$ は $g$ のある制限関数である)で定めると $(V_{A}, <)$ は(集合論の用語で言うところの)木である．

グラフ $G_{A}$ を $(V_{A}, E_{A})$ で $E_{A} = {{f, g} : f < g \lor g < f}$ と定める．

$A_{0}, A_{1}$ を互いに素な $κ^{+}$ の部分集合とする．このとき $G = G_{A_{0}} \otimes G_{A_{1}}$ に対して $χ (G) \leq κ$ が成り立つ．

頂点集合 $V_{A_{0}} \times V_{A_{1}}$ は次の2つの集合の和集合で書ける：
$K_{0} = {(f_{0}, f_{1}) \in V_{A_{0}} \times V_{A_{1}} : dom (f_{0}) < dom (f_{1})} K_{1} = {(f_{0}, f_{1}) \in V_{A_{0}} \times V_{A_{1}} : dom (f_{1}) < dom (f_{0})}$
ここで， $A_{0}$ と $A_{1}$ が互いに素なので， $dom (f_{0}) = dom (f_{1})$ なる点 $(f_{0}, f_{1})$ はないことに注意しよう．

$K_{0}$ と $K_{1}$ それぞれに良い $κ$ 彩色があることを言えばよい．
なぜなら，それができると $V_{A_{0}} \times V_{A_{1}}$ は $2 κ$ 色で良い彩色ができることがわかるが， $2 κ$ は $κ$ と同じ濃度であるからだ．

対称性により $K_{0}$ が $κ$ 色で彩色できることを言おう．
$F : K_{0} \to κ$ を
$F (f_{0}, f_{1}) = f_{1} (dom (f_{0}))$
で定める．
$F$ が良い彩色なことを示そう．
$(f_{0}, f_{1}), (g_{0}, g_{1}) \in K_{0}$ とし， ${(f_{0}, f_{1}), (g_{0}, g_{1})} \in E_{A_{1}} ⋆ E_{A_{2}}$ とする．
$dom (f_{i}) = α_{i}, dom (g_{i}) = β_{i}$ (for $i < 2$ )とおく．
すると $α_{0} < α_{1}$ かつ $β_{0} < β_{1}$ であり，対称性より $α_{1} < β_{1}$ と仮定してよい．
${f_{0}, g_{0}} \in E_{A_{0}}$ より $α_{0} \neq β_{0}$ がわかる．
また ${f_{1}, g_{1}} \in E_{A_{1}}$ より $f_{1} (α_{0}) = g_{1} (α_{0})$ がわかる ( $f_{1}, g_{1}$ が比較可能かつ両方とも $α_{0}$ を定義域に持っているから)．
よって，
$F (f_{0}, f_{1}) = f_{1} (α_{0}) = g_{1} (α_{0}) \neq g_{1} (β_{0}) = F (g_{0}, g_{1})$
となる．ここで $\neq$ は $g_{1}$ の単射性による．

したがって， $F$ が良い彩色なことを示された．

$χ (G_{κ^{+}}) = κ^{+}$ である．

仮に $G_{κ^{+}}$ が $κ$ 色の良い彩色 $c$ を持ったとしよう．
このとき $V_{κ^{+}}$ の長さ $κ^{+}$ の鎖が構成できることを見る．
長さ $κ^{+}$ の鎖 $(t_{α} : α < κ^{+})$ を帰納的に
$t_{0} = \emptyset t_{α + 1} = c_{α}^{⌢} ⟨ c (t_{α}) ⟩ t_{γ} = ⋃_{α < γ} t_{α} (γ は極限順序数)$
と定める．
$c$ が良い彩色なことを使って各 $t_{α}$ が $V_{κ^{+}}$ の元であること (特に各 $t_{α}$ の単射性)を確かめられる．

しかし，すると $⋃_{α < κ^{+}} t_{α}$ は $κ^{+}$ から $κ$ への単射となって矛盾．

$I = {A \subseteq κ^{+} : χ (G_{A}) \leq κ}$ とおくと $I$ は $\leq κ$ 完備の真のイデアルである．

$I$ が部分集合で閉じていることは容易に確かめられる．

$I$ が $κ$ 個の和集合で閉じていることも， $| κ \times κ | = κ$ からわかる．

$I$ が真のイデアルであることは補題4による．

実際にはこのイデアル $I$ が非定常集合イデアルになることが知られているが，その事実はここでは使わないため証明しない．

Hajnalの定理の証明

$(κ^{+}, κ)$ -Ulam行列の存在定理の系として， $κ^{+}$ 上の任意の $\leq κ$ 完備の真のイデアルについて，2つの $I$ 正値集合で互いに素なものがとれることがわかる．

よって，補題5の $I$ にこの事実を適用して互いに素な $A_{0}, A_{1} \subseteq κ^{+}$ で $χ (G_{A_{0}}), χ (G_{A_{1}}) = κ^{+}$ なものがとれる．
互いに素なことから，補題3により， $χ (G_{A_{0}} \otimes G_{A_{1}}) \leq κ$ である．

$χ (G_{A_{0}} \otimes G_{A_{1}}) \geq κ$ については省略する．

これでHajnalの定理が証明された．

最後に無限Hedetniemiの予想についての最近の結果について触れておく．
2017年にRinotによって，ゲーデルの構成可能宇宙 $L$ で任意に後続基数 $κ$ について $χ (G) = χ (H) = κ$ だが、 $χ (G \otimes H) = ℵ_{0}$ なものが構成されている．