Hajnal–Szemerédiの定理

同義語:Hajnal–Szemerédi theoremHajnal-Szemerédiの定理公平彩色equitable coloringequitable colouring

概要

Hajnal–Szemerédiの定理(Hajnal–Szemerédi theorem)とは、最大次数が $r$ 以下の有限グラフは、どの 2 色の頂点の個数の差も $1$ 以下である $r+1$ 色の真の頂点彩色(公平彩色)をもつ、という定理である。Erdős の予想を Hajnal と Szemerédi が証明した。補グラフに言い換えると、頂点数 $ks$ で最小次数が $(k-1)s$ 以上のグラフは、互いに素な $s$ 個の完全グラフ $K_k$ で頂点全体を覆えることになる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: グラフ彩色, 独立集合, 次数(グラフ)

Hajnal–Szemerédiの定理(Hajnal–Szemerédi theorem)とは、最大次数が $r$ 以下の有限グラフは、どの 2 色の頂点の個数の差も $1$ 以下であるような $r+1$ 色の真の頂点彩色(公平彩色)をもつ、という定理である。P. Erdős が 1964 年に予想し、A. Hajnal と E. Szemerédi が 1970 年に長く込み入った論法で証明した(KK08 p. 265)。
最大次数 $r$ のグラフが $r+1$ 色で塗れること自体は、頂点を順に、隣接する頂点が使っていない色で塗る貪欲法で直ちに示せる(グラフ彩色)。この定理の要点は、色の大きさをそろえるという強い制約をつけても、色の数を $r+1$ のまま保てることにある。補グラフに言い換えると、「最小次数が大きいグラフは、完全グラフ $K_k$ の互いに素な写しで頂点全体を覆える」という主張になる(cor-hs-factor)。公平彩色は、仕事の割り当てや負荷の分散の問題に自然に現れ、依存関係が限られた確率変数の和の集中の評価にも使われる(KK08 p. 265)。
この記事では、H. A. Kierstead と A. V. Kostochka による短い証明(KK08)を、細部を補って完全に述べる。

定義と主定理

グラフは有限で単純とする。頂点 $y$ の近傍を $N(y)$、次数を $d(y)$、最大次数を $\Delta(G)$ と書く。頂点集合 $X$ について $N_X(y):=N(y)\cap X$、$d_X(y):=|N_X(y)|$ とおく。頂点の個数を $|G|$、辺の本数を $\|G\|$ と書く。頂点集合 $A,B$ の間の辺の集合を $E(A,B)$ と書く。

公平彩色

グラフ $G$ の 公平な $k$ 彩色(equitable $k$-colouring)とは、頂点集合を $k$ 個の 独立集合 $V_1,\dots,V_k$(色クラス、空でもよい)に分け、どの 2 つの大きさの差も $1$ 以下であるようにすることをいう。

$|G|=n$ なら、公平な $k$ 彩色の色クラスの大きさは $\lfloor n/k\rfloor$ か $\lceil n/k\rceil$ である。

Hajnal–Szemerédi の定理

$r\ge0$ を整数とし、$G$ を $\Delta(G)\le r$ のグラフとする。このとき $G$ は公平な $r+1$ 彩色をもつ。

所在

主張と証明の所在は KK08 Theorem 2.4(p. 268)である。証明は「証明の準備」と「主定理の証明」の節で述べる(prf-thm-hs-main)。

色の数を増やしても成り立つ

$\Delta(G)\le r$ なら、すべての $k\ge r+1$ について $G$ は公平な $k$ 彩色をもつ。

$\Delta(G)\le k-1$ なので、thm-hs-main を $r=k-1$ で使えばよい。$\square$

公平彩色の存在は、色の数について単調とは限らない(ex-hs-nonmonotone)。上の系は、最大次数より多い色数では単調性が回復することを述べている。

完全グラフによる因子

$k,s\ge1$、$n=ks$ とし、$G$ を頂点数 $n$ で最小次数が $(k-1)s$ 以上のグラフとする。このとき $G$ の頂点集合は、どれも 完全グラフ $K_k$ をなす $s$ 個の $k$ 点集合に分けられる。

補グラフ $\overline G$ の各頂点の次数は $n-1-d_G(y)\le ks-1-(k-1)s=s-1$ である。thm-hs-main を $\overline G$ と $r=s-1$ に使うと、$\overline G$ は公平な $s$ 彩色をもち、$n=ks$ なので色クラスの大きさはすべて $k$ である。各色クラスは $\overline G$ で独立、すなわち $G$ で クリーク である。$\square$

$k=2$ のときは、最小次数 $s=n/2$ 以上のグラフが、頂点全体を覆う互いに素な辺の集まりをもつことを述べており、$s\ge2$ なら Diracの定理(Hamilton閉路) の帰結でもある(Hamilton 閉路の辺を 1 本おきにとる)。KK08 p. 265 は、P. Seymour がこの方向の強い予想(最小次数 $\frac{k}{k+1}n$ 以上なら Hamilton 閉路の $k$ 乗を含む)を提起したことを紹介している。

証明の準備

以下、KK08 §2 に沿って thm-hs-main を証明する。$G$ を $\Delta(G)\le r$、$|G|=s(r+1)$ のグラフとする。

ほぼ公平な彩色と補助有向グラフ

$G$ の ほぼ公平な $r+1$ 彩色 とは、$r+1$ 個の色クラスへの分け方で、1 つの色クラス $V^-$ の大きさが $s-1$、1 つの色クラス $V^+$ の大きさが $s+1$、残りの大きさがすべて $s$ であるものをいう。このとき、色クラスを頂点とする 有向グラフ $H=H(G,f)$ を、色クラス $V$ から $W$ への辺があるのは「$V$ のある頂点 $y$ が $W$ に隣接する頂点をもたない」ときと定める。このとき $y$ は $W$ へ 移せる という。$W$ から $V^-$ へ $H$ の有向路(長さ $0$ も含む)があるとき、$W$ は 到達可能 であるという。

到達可能な色クラスの族を $\mathcal A$、その和集合を $A$、$B:=V(G)\setminus A$ とし、$m:=|\mathcal A|-1$、$q:=r-m$ とおく。$V^+\notin\mathcal A$ のとき $|A|=(m+1)s-1$、$|B|=qs+1$ であり、とくに $q\ge1$ である。$y\in B$ は $\mathcal A$ のどの色クラスへも移せない(移せれば $y$ の色クラスが到達可能になる)ので、$\mathcal A$ の $m+1$ 個の色クラスのそれぞれに隣接する頂点をもつ。よって
$$ d_A(y)\ge m+1,\qquad d_B(y)\le r-(m+1)=q-1\qquad(y\in B)\qquad\cdots(1) $$
である。

到達可能なら直せる

$V^+$ が到達可能なほぼ公平な $r+1$ 彩色があれば、$G$ は公平な $r+1$ 彩色をもつ。

$H$ の有向路 $V^+=V_1\to V_2\to\cdots\to V_k=V^-$ をとる(同じ色クラスを 2 度通らないものをとれる)。各 $j< k$ について、$V_j$ の頂点 $y_j$ で $V_{j+1}$ に隣接する頂点をもたないものがある。すべての $j$ について同時に $y_j$ を $V_{j+1}$ へ移すと、$V_1$ は 1 個減り、$V_k$ は 1 個増え、途中の色クラスは 1 個出て 1 個入る。$y_j$ は元の $V_{j+1}$ に隣接せず、$V_{j+1}$ から出ていくのは $y_{j+1}$ だけなので、新しい色クラスも独立である。大きさはすべて $s$ になる。$\square$

以下この節では $V^+\notin\mathcal A$ と仮定する。このとき $m\ge1$ である。実際 $\mathcal A=\{V^-\}$ なら、(1) から $B$ の各頂点は $V^-$ に隣接する頂点をもつので $|E(A,B)|\ge|B|=rs+1$ だが、$|E(A,B)|\le r|V^-|=r(s-1)$ であり矛盾する。
終端的な色クラス。 $W\in\mathcal A$ について、$H$ から $W$ を除いた有向グラフ $H-W$ の中で $V^-$ へ有向路をもつ $\mathcal A\setminus\{W\}$ の色クラスの族を $\mathcal S_W$ とし、$\mathcal T_W:=\mathcal A\setminus(\{W\}\cup\mathcal S_W)$ とおく。$\mathcal T_W=\emptyset$ のとき $W$ を 終端的 という。$m\ge1$ なので $\mathcal T_{V^-}=\mathcal A\setminus\{V^-\}\ne\emptyset$ で、$V^-$ は終端的でない。終端的でない $U\in\mathcal A$ を $|\mathcal T_U|$ が最小になるようにとり、$\mathcal A':=\mathcal T_U$、$t:=|\mathcal A'|\ge1$、$A':=\bigcup\mathcal A'$ とおく。

終端的な色クラスの族
  1. $\mathcal A'$ の色クラスはすべて終端的である。
  2. $\mathcal A'$ の色クラスの頂点は、$\mathcal S_U=(\mathcal A\setminus\mathcal A')\setminus\{U\}$ のどの色クラスへも移せない。とくに $V^-\notin\mathcal A'$、$|A'|=ts$ で、
    $$ d_A(x)\ge m-t\qquad(x\in A')\qquad\cdots(2) $$
    である。

要点:2 は「移せれば $U$ を通らずに $V^-$ へ行ける」ことから、1 は「終端的でない $W\in\mathcal A'$ があれば $\mathcal T_W\subsetneq\mathcal T_U$ となり最小性に反する」ことから従う。

詳しい証明を開く

2:$X\in\mathcal A'$ の頂点が $Y\in\mathcal S_U$ へ移せれば、$X\to Y$ と、$Y$ から $V^-$ への $H-U$ の有向路をつないで、$X$ は $H-U$ の中で $V^-$ へ行けるので $X\in\mathcal S_U$ となり矛盾する。$V^-$ は長さ $0$ の路で自分に到達するので $V^-\in\mathcal S_U\cup\{U\}$、すなわち $V^-\notin\mathcal A'$ であり、$V^+\notin\mathcal A$ なので $\mathcal A'$ の色クラスの大きさはすべて $s$ である。$|\mathcal S_U|=m+1-t-1=m-t$ で、$x\in A'$ は $\mathcal S_U$ の各色クラスに隣接する頂点をもつので (2) が成り立つ。

1:$W\in\mathcal A'$ が終端的でないとし、$Z\in\mathcal T_W$ をとる。$Z\in\mathcal S_U$ なら、$Z$ から $V^-$ への $H-U$ の有向路の色クラスはどれも $H-U$ で $V^-$ へ行けるので $\mathcal S_U\cup\{V^-\}$ に入り、$W\notin\mathcal S_U\cup\{V^-\}$ なので路は $W$ を通らない。これは $Z\in\mathcal T_W$ に反する。$Z=U$ なら、$U\ne V^-$ のとき($U=V^-$ なら $U$ は長さ $0$ の路で $V^-$ に着くので $U\notin\mathcal T_W$)、$U$ から $V^-$ への最短の有向路をとる。これが $W$ を通れば、$W$ から先の部分は $U$ を通らない(最短路は同じ頂点を 2 度通らない)ので $W\in\mathcal S_U$ となり矛盾する。よって路は $W$ を通らず、$U\notin\mathcal T_W$ である。以上から $\mathcal T_W\subset\mathcal A'\setminus\{W\}\subsetneq\mathcal T_U$ であり、$\mathcal T_W\ne\emptyset$ なので $U$ の選び方に反する。$\square$

単独辺。 $z\in W\in\mathcal A'$、$y\in B$ を結ぶ辺 $zy$ が $N_W(y)=\{z\}$ を満たすとき 単独辺 といい、その端点を 単独頂点、互いを 特別な隣人 という。$z$ の特別な隣人($B$ の頂点)の集合を $S_z$、$y\in B$ の特別な隣人($A'$ の頂点)の集合を $S^y$ と書く。$y\in B$ は (1) から $\mathcal A$ の $m+1$ 個の色クラスのそれぞれに隣接する頂点をもち、$d_A(y)\le r-d_B(y)$ なので、2 個以上の隣接頂点をもつ $\mathcal A$ の色クラスは $r-d_B(y)-(m+1)$ 個以下である。残りの $\mathcal A'$ の色クラスではちょうど 1 個なので
$$ |S^y|\ge t-q+1+d_B(y)\qquad(y\in B)\qquad\cdots(3) $$
である。

単独頂点が動かないとき

ある $W\in\mathcal A'$ について、$W$ のどの単独頂点も $\mathcal A\setminus\{W\}$ のどの色クラスへも移せないとする。このとき $q+1\le t$ であり、$B$ のすべての頂点は単独頂点である。

辺の本数を 2 通りに数える

$W$ の単独頂点の集合を $S$、$D:=W\setminus S$ とする。$y\in B$ は $W$ に隣接する頂点をもち((1))、それが 1 個なら $y$ はある $z\in S$ の特別な隣人である。よって $S$ の頂点に隣接しない $y\in B$ は $W$ に 2 個以上の隣接頂点をもち、
$$ |E(W,B)|\ge|N_B(S)|+2\bigl(|B|-|N_B(S)|\bigr)=2|B|-|N_B(S)| $$
である。$z\in S$ は $\mathcal A\setminus\{W\}$ の $m$ 個の色クラスのそれぞれに隣接する頂点をもつので $d_B(z)\le r-m=q$ であり、$|N_B(S)|\le q|S|$ である。また (2) から $x\in W$ は $d_B(x)\le r-(m-t)=q+t$ を満たす。よって $|S|+|D|=s$ を使って
$$ qs+q|D|+2=2(qs+1)-q|S|\le|E(W,B)|\le q|S|+(q+t)|D|=qs+t|D| $$
となり、$(t-q)|D|\ge2$、とくに $t\ge q+1$ である。すると (3) から $|S^y|\ge2$ となり、$B$ の各頂点は単独頂点である。$\square$

動かせる単独頂点の存在

ある $W\in\mathcal A'$ と単独頂点 $z\in W$ があって、$z$ は $\mathcal A\setminus\{W\}$ のある色クラスへ移せるか、$z$ は互いに隣接しない 2 つの特別な隣人をもつ。

重みを配る

結論が成り立たないとすると、どの $W\in\mathcal A'$ にも lem-hs-solo が使えて、$q+1\le t$ で $B$ の頂点はすべて単独頂点である。また単独頂点 $z\in A'$ の $S_z$ はどれも クリーク である。単独辺 $xy$($x\in A'$、$y\in B$)に重み $\mu(xy):=q/|S_x|$ を、それ以外の $E(A',B)$ の辺に $0$ を置く。単独頂点 $z\in A'$ から出る重みの和は $|S_z|\cdot q/|S_z|=q$ なので、全体の重みは $q|A'|=qst$ 以下である。
一方 $y\in B$ について、$c_y:=\max\{|S_z|\mid z\in S^y\}$ とし、$c_y=|S_z|$ となる $z$ をとる。$S_z$ は $y$ を含むクリークなので $c_y-1\le d_B(y)\le q-1$((1))、すなわち $c_y\le q$ である。(3) と $d_B(y)\ge c_y-1$ から
$$ \sum_{z\in S^y}\frac q{|S_z|}\ge|S^y|\frac q{c_y}\ge(t-q+c_y)\frac q{c_y}=(t-q)\frac q{c_y}+q\ge t $$
である($t-q\ge1$、$q/c_y\ge1$)。よって全体の重みは $t|B|=t(qs+1)>qst$ 以上となり、矛盾する。$\square$

主定理の証明

2 重の帰納法

頂点数の調整。 $|G|=s(r+1)-p$($1\le p\le r$)なら、$G$ に互いに素な $K_p$ を加えた $G'$ は $|G'|=s(r+1)$、$\Delta(G')\le r$ を満たす。$G'$ の公平な $r+1$ 彩色では色クラスの大きさはすべて $s$ で、$K_p$ の $p$ 頂点は別々の色クラスにあるので、$G$ に制限すると大きさ $s$ か $s-1$ の公平彩色になる。よって次を示せばよい:$r\ge0$、$(r+1)\mid|G|$、$\Delta(G)\le r$ なら $G$ は公平な $r+1$ 彩色をもつ。 これを $\|G\|$ についての帰納法で示す($r$ はすべての値を同時に扱う)。$\|G\|=0$ なら任意に大きさ $s$ ずつに分ければよい。
ほぼ公平な彩色を作る。 辺 $e=xy$ をとる。帰納法の仮定から $G-e$ は公平な $r+1$ 彩色 $f_0$ をもつ。$x,y$ が別の色クラスなら $f_0$ が $G$ の公平彩色である。同じ色クラス $V$ にあるとき、$x$ の $V$ の外の隣接頂点は $r-1$ 個以下なので、残り $r$ 個の色クラスのどれかは $x$ に隣接する頂点をもたない。$x$ をそこへ移すと、$G$ のほぼ公平な彩色 $f$($V^-=V\setminus\{x\}$)が得られる。
$q$ についての帰納法。 「$G$ のほぼ公平な彩色 $f$ があれば $G$ は公平彩色をもつ」を $q(f)$ についての帰納法で示す。$V^+\in\mathcal A$ なら lem-hs-path で終わる($q=0$ なら $r+1$ 個すべてが到達可能なのでこの場合である)。$V^+\notin\mathcal A$ なら、lem-hs-discharge の $W\in\mathcal A'$ と単独頂点 $z\in W$ をとる。$z$ が $\mathcal A\setminus\{W\}$ のある色クラスへ移せるなら $y_1\in S_z$ を任意にとり、移せないなら互いに隣接しない $y_1,y_2\in S_z$ をとる。$B^-:=B\setminus\{y_1\}$ は $|B^-|=qs$ で、(1) から $\Delta(G[B^-])\le q-1$ である。$A$ と $B$ の間に辺があるので $\|G[B^-]\|<\|G\|$ であり、帰納法の仮定($r$ を $q-1$ にしたもの)から $G[B^-]$ は公平な $q$ 彩色 $g$(色クラスの大きさはすべて $s$)をもつ。
場合 1:$z$ が $X\in\mathcal A\setminus\{W\}$ へ移せる。 $A^+:=A\cup\{y_1\}$ の上で、$z$ を $X$ へ、$y_1$ を $W\setminus\{z\}$ へ移す($y_1$ の $W$ の中の隣接頂点は $z$ だけなので独立性は保たれる)。$X=V^-$ なら、得られた $m+1$ 色の彩色の色クラスはすべて大きさ $s$ で公平である。そうでなければ、$X\cup\{z\}$ を $V^+$ とする $G[A^+]$ のほぼ公平な彩色 $\varphi$ が得られる。$W$ は終端的なので(lem-hs-terminal)、$X$ から $V^-$ への有向路で $W$ を通らないものがあり、その路の色クラスと、それらの間の辺は $\varphi$ でも変わらない($X$ は頂点 $z$ が増えただけで、$X$ から出る辺は保たれる)。よって $V^+(\varphi)$ は到達可能で、lem-hs-path から $G[A^+]$ は公平な $m+1$ 彩色 $\varphi'$ をもつ(lem-hs-path の証明は最大次数の条件を使わないので、色の数を $m+1$ にした $G[A^+]$ にもそのまま使える)。$\varphi'$ と $g$ を合わせると、色クラスがすべて大きさ $s$ の $G$ の公平な $r+1$ 彩色になる。
場合 2:$z$ は $\mathcal A\setminus\{W\}$ のどの色クラスへも移せない。 $y_1,y_2$ は上でとったものである。$z$ は $\mathcal A\setminus\{W\}$ の $m$ 個の色クラスと $y_1$ に隣接するので $d_{B^-}(z)\le r-(m+1)=q-1$ であり、$g$ のある色クラス $Y$ は $z$ に隣接する頂点をもたない。$z$ を $Y$ へ、$y_1$ を $W$ へ移し、$W^*:=(W\setminus\{z\})\cup\{y_1\}$ とする。得られる彩色 $\psi$ は $Y\cup\{z\}$ を $V^+$、元の $V^-$ を $V^-$ とする $G$ のほぼ公平な彩色である。$\mathcal A\setminus\{W\}$ の色クラスは、$W$ を通らない有向路がそのまま残るので $\psi$ でも到達可能である。$W$ から出る $H$ の辺 $W\to Z$($Z\in\mathcal A$)を与える頂点は $z$ ではないので $W^*$ に残り、$W^*\to Z$ も残る。よって $W^*$ も到達可能である。さらに $y_2$ の $W$ の中の隣接頂点は $z$ だけで、$y_2$ は $y_1$ に隣接しないので、$y_2$ は $W^*$ へ移せる。$y_2$ の色クラスは $B$ の側にあるので、到達可能な色クラスは $m+2$ 個以上になり、$q(\psi)< q(f)$ である。帰納法の仮定から $G$ は公平彩色をもつ。$\square$

証明は 2 つの帰納法を組み合わせた構成的なもので、KK08 Theorem 3.2(p. 269)は、これを整理すると頂点数 $n$ について $O(n^5)$ 回の手順で公平な $r+1$ 彩色を作る算法が得られることを示している。

例

等号の例:奇数の完全二部グラフ

$m$ を奇数とし、完全二部グラフ $K_{m,m}$ を考える。最大次数は $m$ である。公平な $m$ 彩色があれば、頂点数 $2m$ なので色クラスの大きさはすべて $2$ である。各色クラスは独立なので片側に収まり、片側の $m$ 頂点が大きさ $2$ の色クラスで分けられることになるが、$m$ は奇数なので不可能である。よって $K_{m,m}$ は $\Delta+1=m+1$ 色を必要とし、thm-hs-main の色の数は一般には減らせない。完全グラフ $K_{r+1}$ も、彩色数 が $r+1$ なので同じく等号の例である。

公平彩色の色数は単調でない

$K_{3,3}$ は両側をそれぞれ色クラスにすれば公平な 2 彩色をもつ。しかし ex-hs-tight から公平な 3 彩色をもたない。最大次数は $3$ なので、cor-hs-more-colours から $k\ge4$ では公平な $k$ 彩色をもつ。

星グラフ

中心 1 個と葉 $\ell$ 個からなる星 $K_{1,\ell}$ は 2 色で塗れる(彩色数 は $2$)。しかし公平な $k$ 彩色では、中心の色クラスは中心だけ(葉はすべて中心に隣接する)で大きさ $1$ なので、ほかの色クラスの大きさは $2$ 以下であり、$\ell\le2(k-1)$、すなわち $k\ge\frac\ell2+1$ が必要である。逆に $k\ge\frac\ell2+1$ なら、葉を残りの $k-1$ 色に、$\ell\le k-1$ のときは $1$ 個以下ずつ、そうでなければ $1$ 個か $2$ 個ずつ分ければ公平彩色になる。彩色数を最大次数の代わりに使うことはできない。

反例:仮定を外すと成り立たないこと

外す仮定例成り立たなくなること
thm-hs-main の色の数 $r+1$($r$ 色に減らす)$K_{3,3}$($r=3$)公平な 3 彩色がない
cor-hs-more-colours の $k\ge\Delta+1$$K_{3,3}$、$k=3$(公平な 2 彩色はある)公平な $k$ 彩色がない
thm-hs-main の「最大次数 $\le r$」(「彩色数 $\le r+1$」に替える)$K_{1,4}$、$r=1$公平な 2 彩色がない
cor-hs-factor の最小次数 $(k-1)s$($1$ だけ下げる)$k=2$、$s=3$、$K_{2,4}$最小次数 $2=(k-1)s-1$ で、$K_2$ による因子がない
反例の表の確かめ

1・2 行目は ex-hs-tight・ex-hs-nonmonotone である。3 行目:$K_{1,4}$ の彩色数は $2$ だが、ex-hs-star から公平な $k$ 彩色には $k\ge3$ が必要である。4 行目:$K_{2,4}$ は頂点数 $6$、小さい側の 2 頂点の次数は $4$、大きい側の 4 頂点の次数は $2$ なので最小次数は $2$ である。互いに素な 3 本の辺で頂点全体を覆うと、大きい側の 4 頂点はそれぞれ小さい側の頂点と組になるが、小さい側は 2 頂点しかないので不可能である。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する