Combinatorial Nullstellensatz
概要
Combinatorial Nullstellensatz（組合せ論的零点定理、combinatorial Nullstellensatz）とは、体の有限部分集合 $S_1,\dots,S_n$ の直積の上の多項式についての Alon の 2 つの定理である。第 1 形は、直積の上で消える多項式が $\prod_{s\in S_i}(x_i-s)$ たちの 1 次結合として次数を抑えて書けると主張する。第 2 形は、全次数 $\sum_it_i$ の多項式の $x_1^{t_1}\cdots x_n^{t_n}$ の係数が $0$ でなく $\lvert S_i\rvert>t_i$ なら、直積のどこかで値が $0$ でないと主張する。Cauchy–Davenport の定理、Erdős–Heilbronn の予想、リスト彩色の Alon–Tarsi の定理などが導ける。
Combinatorial Nullstellensatz（組合せ論的零点定理）とは、体 $K$ 上の多項式が、各変数の値を有限集合 $S_1,\dots,S_n\subset K$ から選んだ「格子」$S_1\times\cdots\times S_n$ の上でどう振る舞うかを述べた Alon の 2 つの定理である。第 1 形は、格子の上で消える多項式が $\prod_{s\in S_i}(x_i-s)$ たちの生成するイデアルに、係数の多項式の次数を抑えた形で入ることを述べ、第 2 形は、ある最高次の単項式の係数が $0$ でなければ格子のどこかで値が $0$ でないことを述べる。第 2 形は「組合せ論的な対象の存在」を「多項式の 1 つの係数が $0$ でないこと」に帰着させる道具で、加法的整数論・グラフの彩色・グラフの部分グラフの存在などに応用がある（Alo99）。
名前は Hilbertの零点定理 にちなむ。Hilbert の零点定理は、代数閉体 $K$ の上で $f$ が $g_1,\dots,g_m$ の共通零点すべてで消えれば、ある $k\ge1$ について $f^k=\sum_ih_ig_i$ と書けることを主張する。共通零点が格子 $S_1\times\cdots\times S_n$ で、$g_i$ が 1 変数の多項式 $\prod_{s\in S_i}(x_i-s)$ である特別な場合には、$K$ が代数閉でなくても $k=1$ でよく、$h_i$ の次数まで抑えられる。これが第 1 形である。
記号と主張
以下 $K$ を体とする。$f\in K[x_1,\dots,x_n]$ の全次数を $\deg f$、変数 $x_i$ についての次数を $\deg_{x_i}f$ と書く。$t=(t_1,\dots,t_n)$ が非負整数の組のとき $x^t:=x_1^{t_1}\cdots x_n^{t_n}$ とし、$f$ の $x^t$ の係数を $[x^t]f$ と書く。$S_1,\dots,S_n\subset K$ を空でない有限集合とし、
$$
S:=S_1\times\cdots\times S_n,\qquad g_i(x_i):=\prod_{s\in S_i}(x_i-s)\quad(i=1,\dots,n)
$$
とおく。$g_i$ は $x_i$ だけの、最高次の係数が $1$ の $\lvert S_i\rvert$ 次多項式で、$S_i$ の上で消える。
証明には次の補題を使う。
$P\in K[x_1,\dots,x_n]$ が $\deg_{x_i}P<\lvert S_i\rvert$（$i=1,\dots,n$）をみたし、$S$ のすべての点で $0$ なら $P=0$ である。
要点：$n=1$ は根の個数が次数以下であることで、$n\ge2$ は $x_n$ の多項式とみて係数ごとに帰納法の仮定を使う。
詳しい証明を開く
$n=1$ では、$0$ でない 1 変数多項式の根の個数は次数以下であることによる。$n\ge2$ とし、$P=\sum_{j}P_j(x_1,\dots,x_{n-1})x_n^j$ と書く。$(s_1,\dots,s_{n-1})\in S_1\times\cdots\times S_{n-1}$ を固定すると、$x_n$ の多項式 $\sum_jP_j(s_1,\dots,s_{n-1})x_n^j$ は次数が $\lvert S_n\rvert$ 未満で $S_n$ の全点で消えるので $0$ であり、各 $P_j$ は $S_1\times\cdots\times S_{n-1}$ で消える。$\deg_{x_i}P_j\le\deg_{x_i}P$ なので帰納法の仮定から $P_j=0$、よって $P=0$ である。$\square$
多項式法 の補題「格子の上で消える多項式」と同じ内容である。
第 1 形
$f\in K[x_1,\dots,x_n]$ が $S$ のすべての点で $0$ になるとする。このとき
$$
f=\sum_{i=1}^nh_ig_i,\qquad \deg h_i\le\deg f-\lvert S_i\rvert\quad(i=1,\dots,n)
$$
をみたす $h_1,\dots,h_n\in K[x_1,\dots,x_n]$ がある（$h_i=0$ のときは次数の条件を課さない）。さらに、$K$ の部分環 $R$ が $f$ と $g_1,\dots,g_n$ の係数をすべて含むなら、$h_i$ を $R[x_1,\dots,x_n]$ の中にとれる。
$R_0$ を $f$ と $g_1,\dots,g_n$ の係数で生成される $K$ の部分環とする（$R\supset R_0$ である）。$d_i:=\lvert S_i\rvert$ とおく。
段 1（1 つの $g_i$ での割り算）．$F\in R_0[x_1,\dots,x_n]$ を $F=\sum_kc_kx_i^k$（$c_k$ は $x_i$ を含まない）と書く。$g_i$ は最高次の係数が $1$ なので、係数を $R_0$ に保ったまま 1 変数の割り算ができ、$x_i^k=a_kg_i+b_k$（$a_k,b_k\in R_0[x_i]$、$\deg b_k< d_i$）と書ける。$k< d_i$ なら $a_k=0$、$b_k=x_i^k$ で、$k\ge d_i$ なら $\deg a_k=k-d_i$、$\deg b_k< d_i\le k$ である。$q:=\sum_kc_ka_k$、$r:=\sum_kc_kb_k$ とおくと $F=qg_i+r$ で、
$$
\deg q\le\deg F-d_i,\qquad \deg r\le\deg F,\qquad \deg_{x_i}r< d_i,\qquad \deg_{x_j}r\le\deg_{x_j}F\ (j\neq i)
$$
が成り立つ（$\deg(c_ka_k)\le\deg c_k+k-d_i$ と $\deg(c_kb_k)\le\deg c_k+k$ を使う。$a_k,b_k$ は $x_i$ だけの多項式なので、ほかの変数の次数は増えない）。
段 2（順に割る）．$r_0:=f$ とし、$i=1,\dots,n$ の順に $r_{i-1}$ を段 1 で $g_i$ で割って $r_{i-1}=h_ig_i+r_i$ とする。段 1 の評価から $\deg r_i\le\deg f$、$\deg h_i\le\deg f-d_i$ であり、$g_i$ で割っても $j< i$ についての $\deg_{x_j}r_i< d_j$ は保たれる。よって
$$
f=\sum_{i=1}^nh_ig_i+r_n,\qquad \deg_{x_i}r_n< d_i\ (i=1,\dots,n)
$$
で、すべての係数は $R_0$ にある。
段 3．$f$ と各 $g_i$ は $S$ の上で消えるので $r_n$ も $S$ の上で消え、lem-cn-grid により $r_n=0$ である。$\square$
Alo99 の §2 の証明は、$S_i$ の点で成り立つ関係 $x_i^{d_i}=x_i^{d_i}-g_i(x_i)$（右辺は $x_i$ について次数 $d_i-1$ 以下）で $f$ の高い冪を次々に置き換えるもので、段 1・段 2 はその置き換えを割り算として整理したものである。
第 2 形
$f\in K[x_1,\dots,x_n]$ の全次数が $t_1+\cdots+t_n$（$t_i\ge0$ は整数）で、$[x^t]f\neq0$ とする。$\lvert S_i\rvert>t_i$（$i=1,\dots,n$）なら、$f(s_1,\dots,s_n)\neq0$ となる $(s_1,\dots,s_n)\in S$ がある。
各 $S_i$ を $t_i+1$ 元の部分集合に取り替えてよい（小さい格子で値が $0$ でない点があればよい）。$f$ が $S$ の上で消えると仮定すると、thm-cn-first により $f=\sum_ih_ig_i$、$\deg h_i\le\deg f-t_i-1$ である。$h_ig_i$ の全次数 $\deg f$ の部分は、$h_i$ の全次数 $\deg f-t_i-1$ の部分と $x_i^{t_i+1}$ の積なので、そこに現れる単項式の $x_i$ の指数は $t_i+1$ 以上である。全次数が $\deg f$ 未満の単項式は $x^t$ と異なる。よって右辺の $x^t$ の係数は $0$ で、$[x^t]f\neq0$ に反する。$\square$
どちらも Alo99 の Theorem 1.1・1.2 である。第 2 形の仮定「全次数が $t_1+\cdots+t_n$」は、$x^t$ が $f$ の最高次の単項式の 1 つであることを言っている。第 2 形は、次の節の係数の公式から直接にも導ける（cor-cn-second-from-formula）。
係数を格子の上の値で表す公式
第 2 形は、最高次の係数を格子の上の値の重み付きの和として書く次の公式からも分かる。$\lvert S_i\rvert=t_i+1$ のとき、$s\in S_i$ について
$$
\varphi_i(s):=\prod_{u\in S_i,\ u\neq s}(s-u)\ (\neq0)
$$
とおく（$\varphi_i(s)=g_i'(s)$ である）。
$\lvert S_i\rvert=t_i+1$（$i=1,\dots,n$）とし、$f\in K[x_1,\dots,x_n]$ の全次数が $t_1+\cdots+t_n$ 以下とする。このとき
$$
[x^t]f=\sum_{(s_1,\dots,s_n)\in S}\frac{f(s_1,\dots,s_n)}{\varphi_1(s_1)\cdots\varphi_n(s_n)}
$$
が成り立つ。
要点：右辺は $f$ について線形で、単項式 $x^\alpha$ では変数ごとの和の積に分かれる。1 変数では Lagrange補間 の最高次の係数を比べると、指数が $t_i$ 以下のとき和は $[\alpha_i=t_i]$ になる。
詳しい証明を開く
右辺を $L(f)$ とおくと、$L$ は $f$ について $K$ 線形なので、$\lvert\alpha\rvert:=\alpha_1+\cdots+\alpha_n\le t_1+\cdots+t_n$ をみたす単項式 $x^\alpha$ について $L(x^\alpha)=[\alpha=t]$（$\alpha=t$ なら $1$、そうでなければ $0$）を示せばよい。$L(x^\alpha)=\prod_{i=1}^nL_i(\alpha_i)$、$L_i(a):=\sum_{s\in S_i}s^a/\varphi_i(s)$ と変数ごとに分かれる。
$0\le a\le t_i$ なら $L_i(a)=[a=t_i]$ である。実際、$x^a$ は次数 $t_i$ 以下なので Lagrange 補間の公式により $$x^a=\sum_{s\in S_i}s^a\prod_{u\in S_i,\ u\neq s}\frac{x-u}{s-u}$$ であり、右辺の各項 $\prod_{u\neq s}(x-u)$ は最高次の係数 $1$ の $t_i$ 次式なので、両辺の $x^{t_i}$ の係数を比べると $[a=t_i]=\sum_{s\in S_i}s^a/\varphi_i(s)$ となる。
$\alpha\neq t$ とする。すべての $i$ で $\alpha_i\le t_i$ なら、ある $i$ で $\alpha_i< t_i$ である。ある $j$ で $\alpha_j>t_j$ なら、$\lvert\alpha\rvert\le\lvert t\rvert$ からやはりある $i$ で $\alpha_i< t_i$ である。どちらの場合も $L_i(\alpha_i)=0$ なので $L(x^\alpha)=0$ である。$\alpha=t$ なら $L(x^t)=\prod_iL_i(t_i)=1$ である。$\square$
thm-cn-second の仮定のもとで、$S_i$ を $t_i+1$ 元の部分集合に取り替えると、thm-cn-coefficient-formula により $[x^t]f$ は $f$ の $S$ の上の値の 1 次結合である。$[x^t]f\neq0$ なので、$S$ の上の値のどれかは $0$ でない。
条件を外すと
第 2 形（thm-cn-second）の仮定を 1 つずつ外すと、次のように結論が成り立たなくなる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $\lvert S_i\rvert>t_i$ | $n=2$、$f=x_1x_2$、$t=(1,1)$、$S_1=\{0,1\}$、$S_2=\{0\}$ | $f$ は $S_1\times S_2$ の全点で $0$ になる |
| $\deg f=t_1+\cdots+t_n$ | $n=1$、$f=x_1-x_1^2$、$t_1=1$、$S_1=\{0,1\}$ | $[x_1]f=1\neq0$ だが $f$ は $S_1$ の全点で $0$ |
| $K$ が体 | $\mathbb{Z}/6\mathbb{Z}$ 上の $f=2x_1$、$t_1=1$、$S_1=\{0,3\}$ | $[x_1]f=2\neq0$ だが $f(3)=6=0$ |
1 行目は $\lvert S_2\rvert=1=t_2$、2 行目は $\deg f=2>t_1$ で、ほかの仮定はみたしている。3 行目は零因子 $2\cdot3=0$ のため、lem-cn-grid の $n=1$ の場合（根の個数は次数以下）が成り立たない。第 2 形の逆（格子の上で $0$ でない点があれば $[x^t]f\neq0$）は成り立たない。たとえば $\mathbb{Q}$ 上の $f=x_1^2+x_2^2$、$t=(1,1)$、$S_1=S_2=\{0,1\}$ では全次数は $2=t_1+t_2$ で $[x_1x_2]f=0$ だが、$f(1,0)=1\neq0$ である。
応用 1：加法的整数論
$p$ を素数とし、$\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}$ の部分集合 $A,B$ について $A+B:=\{a+b\mid a\in A,\ b\in B\}$ と書く。
Cauchy–Davenport の定理（$A,B\neq\emptyset$ なら $\lvert A+B\rvert\ge\min\{p,\lvert A\rvert+\lvert B\rvert-1\}$）は、第 2 形を $f(x,y)=\prod_{c\in C}(x+y-c)$（$C\supset A+B$）に当てて示せる。証明と、組合せ論的な原証明・等号の場合・一般のアーベル群への拡張は Cauchy–Davenportの定理 にまとめた。ここでは、和に「相異なる」という制限をつけた場合を扱う。$A\subset\mathbb{F}_p$ について
$$
A\mathbin{\hat{+}}A:=\{a+a'\mid a,a'\in A,\ a\neq a'\}
$$
とおく。Erdős と Heilbronn は 1964 年に次の下界を予想した（Alo99 §4）。
$p$ を素数、$A\subset\mathbb{F}_p$ を空でない部分集合とすると、$\lvert A\mathbin{\hat{+}}A\rvert\ge\min\{p,\ 2\lvert A\rvert-3\}$ である。
$k:=\lvert A\rvert$ とおく。$k=1$ なら右辺は負で、$k=2$ なら $A\mathbin{\hat{+}}A$ は $1$ 元で右辺は $1$ なので、$k\ge3$ としてよい。
$2k-3\le p$ の場合．$\lvert A\mathbin{\hat{+}}A\rvert\le2k-4$ と仮定し、$A\mathbin{\hat{+}}A\subset E$、$\lvert E\rvert=2k-4$ となる $E\subset\mathbb{F}_p$ をとる（$2k-4< p$ なのでとれる）。
$$
Q(x,y):=(x-y)\prod_{e\in E}(x+y-e)
$$
とおく。$(a,a')\in A\times A$ について、$a=a'$ なら第 1 因子が、$a\neq a'$ なら $a+a'\in E$ により第 2 因子が $0$ になるので、$Q$ は $A\times A$ の全点で $0$ である。$Q$ の全次数は $2k-3=(k-1)+(k-2)$ で、最高次の部分は $(x-y)(x+y)^{2k-4}$ である。$N:=2k-4$ とおくと
$$
[x^{k-1}y^{k-2}]Q=\binom{N}{k-2}-\binom{N}{k-1}=\binom{N}{k-2}\Bigl(1-\frac{k-2}{k-1}\Bigr)=\frac{N!}{(k-1)!\,(k-2)!}
$$
で、これは Catalan数 $C_{k-2}$ に等しい。$N< p$ なので $N!$ は $p$ で割り切れず、この係数は $\mathbb{F}_p$ で $0$ でない。thm-cn-second（$t=(k-1,k-2)$、$S_1=S_2=A$、$\lvert A\rvert=k$）により $Q(a,a')\neq0$ となる点があり、矛盾する。
$2k-3>p$ の場合．$p=2$ では $k\le2$ なのでこの場合は起こらず、$p$ は奇数である。$k>(p+3)/2$ なので、$\lvert A'\rvert=(p+3)/2$ の部分集合 $A'\subset A$ がとれる。$2\lvert A'\rvert-3=p$ なので前の場合から $\lvert A\mathbin{\hat{+}}A\rvert\ge\lvert A'\mathbin{\hat{+}}A'\rvert\ge p$ である。$\square$
$p=7$、$A=\{0,1,2,3\}$ では $A\mathbin{\hat{+}}A=\{1,2,3,4,5\}$ で、等号 $5=2\cdot4-3$ が成り立つ。この予想は Dias da Silva と Hamidoune が、$A$ の相異なる $s$ 元の和の集合 $s^\wedge A$ について $\lvert s^\wedge A\rvert\ge\min\{p,\ s\lvert A\rvert-s^2+1\}$ という形で、線形代数と対称群の表現論の道具を使って最初に証明した（Alo99 Theorem 4.3・4.6 と §4 の記述。この記事では一般の $s$ の場合を証明しない）。上の多項式による証明は Alon–Nathanson–Ruzsa の方法で、$Q$ の因子 $x-y$ を一般の多項式 $h$ に替えた「$h(a_0,\dots,a_k)\neq0$ という制限つきの和」の下界（Alo99 Theorem 4.1）の特別な場合である。
応用 2：Chevalley–Warning の定理
$p$ を素数とし、$P_1,\dots,P_m\in\mathbb{F}_p[x_1,\dots,x_n]$ が $\sum_{i}\deg P_i< n$ をみたすとする。$P_1,\dots,P_m$ が共通零点 $c=(c_1,\dots,c_n)$ をもてば、$c$ と異なる共通零点ももつ。
$c$ が唯一の共通零点だと仮定し、
$$
F(x):=\prod_{i=1}^m\bigl(1-P_i(x)^{p-1}\bigr)-\delta\prod_{j=1}^n\prod_{u\in\mathbb{F}_p,\ u\neq c_j}(x_j-u)
$$
とおく。$\delta\in\mathbb{F}_p$ は $F(c)=0$ となるように選ぶ。第 2 項の $x=c$ での値は $\delta\bigl((p-1)!\bigr)^n=\delta(-1)^n$（Wilsonの定理）なので $\delta=(-1)^n\neq0$ である。$x\neq c$ なら、ある $P_i(x)\neq0$ なので Fermatの小定理 により $P_i(x)^{p-1}=1$ となって第 1 項は $0$、ある $x_j\neq c_j$ なので第 2 項も $0$ である。よって $F$ は $\mathbb{F}_p^n$ 全体で $0$ である。一方、第 1 項の全次数は $(p-1)\sum_i\deg P_i<(p-1)n$ で、第 2 項は全次数 $(p-1)n$、$x_1^{p-1}\cdots x_n^{p-1}$ の係数は $-\delta\neq0$ なので、$F$ についてこの単項式は最高次で係数は $-\delta$ である。thm-cn-second（$S_i=\mathbb{F}_p$、$t_i=p-1$）により $F$ は $0$ でない値をとり、矛盾する。$\square$
これは Alo99 Theorem 3.1 の証明である。共通零点の個数が $p$ で割り切れるというより強い主張（素数冪の位数の有限体でも成り立つ）は Chevalley–Warningの定理 で、冪の和による別の方法で証明している。
応用 3：正則な部分グラフ
自己ループのない多重グラフ $G=(V,E)$ の部分グラフで、どの頂点の次数も $p$ であるもの（$p$-正則な部分グラフ）を探す。辺を変数にとり、「辺を選ぶ／選ばない」を $\{0,1\}$ の値で表す。
$p$ を素数とする。自己ループのない多重グラフ $G=(V,E)$ の平均次数が $2p-2$ より大きく、最大次数が $2p-1$ 以下なら、$G$ は $p$-正則グラフである部分グラフ（辺が $1$ 本以上）を含む。
頂点 $v$ と辺 $e$ について、$v$ が $e$ の端点なら $a_{v,e}:=1$、そうでなければ $a_{v,e}:=0$ とし、$\mathbb{F}_p$ 上で
$$
F:=\prod_{v\in V}\Bigl[1-\Bigl(\sum_{e\in E}a_{v,e}x_e\Bigr)^{p-1}\Bigr]-\prod_{e\in E}(1-x_e)
$$
とおく。平均次数 $2\lvert E\rvert/\lvert V\rvert>2p-2$ から、第 1 項の全次数は $(p-1)\lvert V\rvert$ 以下で $\lvert E\rvert$ より小さい。第 2 項は全次数 $\lvert E\rvert$、$\prod_ex_e$ の係数は $-(-1)^{\lvert E\rvert}\neq0$ である。thm-cn-second（$S_e=\{0,1\}$、$t_e=1$）から $F(x)\neq0$ となる $x\in\{0,1\}^E$ がある。$F(0)=1-1=0$ なので $x\neq0$ で、第 2 項は $0$、よって第 1 項は $0$ でない。すなわち各 $v$ で $\bigl(\sum_ea_{v,e}x_e\bigr)^{p-1}\neq1$ で、Fermatの小定理 から $\sum_ea_{v,e}x_e\equiv0\pmod p$ である。$x_e=1$ の辺の全体 $H$ は空でなく、$H$ での各頂点の次数は $p$ の倍数で $2p-1$ 以下なので $0$ か $p$ である。次数 $p$ の頂点と $H$ の辺が求める部分グラフである。$\square$
$p=3$ では、4-正則な多重グラフに辺を 1 本加えたもの（平均次数が $4$ より大きく、最大次数 $5$）は 3-正則な部分グラフを含む（Alo99 Theorem 6.1 と前の段落）。
応用 4：グラフの彩色と Alon–Tarsi の定理
単純グラフ $G$ の頂点を $1,\dots,n$ とし、各頂点 $i$ に色のリスト $L_i$ を与える。各 $i$ に $L_i$ の色を選び、隣り合う頂点の色が異なるようにできるとき、$L$ から彩色できるという。頂点ごとの大きさ $\lvert L_i\rvert=\ell(i)$ のどんなリストからも彩色できるとき、$G$ は $\ell$-選択可能（$\ell$-choosable）であるという（定数 $k$ のときが 五色定理 の定義「リスト彩色と選択数」の $k$-選択可能）。色は有限個しか使わないので、リストは $\mathbb{Q}$ の部分集合としてよい。グラフ多項式を
$$
f_G(x_1,\dots,x_n):=\prod_{\{i,j\}\in E,\ i< j}(x_i-x_j)
$$
で定める。色の選び方 $c=(c_1,\dots,c_n)$ が隣り合う頂点に異なる色を与えることは $f_G(c)\neq0$ と同値である。
$G$ の各辺に向きをつけた有向グラフ $D$ を $G$ の向き付けという。$D$ の辺の部分集合 $H$ が、どの頂点でも $H$ の中の入次数と出次数が等しいとき、$H$ を $D$ の Euler 部分グラフとよぶ（空集合も含め、連結とは限らない）。辺の数が偶数のものの個数を $\mathrm{EE}(D)$、奇数のものの個数を $\mathrm{EO}(D)$ とする。
$D$ を $G$ の向き付けとし、頂点 $i$ の出次数を $d_i$ とすると、$[x_1^{d_1}\cdots x_n^{d_n}]f_G=\pm\bigl(\mathrm{EE}(D)-\mathrm{EO}(D)\bigr)$ である。
要点：積を展開すると各項は向き付けに対応し、出次数の同じ向き付けは $D$ の Euler 部分グラフと 1 対 1 に対応する。
詳しい証明を開く
$f_G$ の展開で、辺 $\{i,j\}$（$i< j$）の因子から $x_i$ を選ぶことを「$i\to j$ と向ける」、$-x_j$ を選ぶことを「$j\to i$ と向ける」と読む。各項は向き付け $D'$ に対応し、その単項式は $\prod_ix_i^{(D'\text{ での }i\text{ の出次数})}$、符号は $(-1)^{\sigma(D')}$（$\sigma(D')$ は番号の大きい頂点から小さい頂点へ向いた辺の数）である。よって $[x^d]f_G=\sum_{D'}(-1)^{\sigma(D')}$（和は出次数が $d=(d_1,\dots,d_n)$ の向き付け全体）である。
出次数が $d$ の向き付け $D'$ に、$D$ と $D'$ で向きの異なる辺の集合 $H$（$D$ の向きで考える）を対応させる。頂点 $v$ の $D'$ での出次数は、$D$ での出次数から $H$ での出次数を引き、$H$ での入次数を足したものなので、$H$ は Euler 部分グラフである。逆に Euler 部分グラフ $H$ の向きを逆にすると出次数が $d$ の向き付けが得られ、この対応は全単射である。辺 1 本の向きを逆にすると $\sigma$ の偶奇が変わるので $(-1)^{\sigma(D')}=(-1)^{\sigma(D)}(-1)^{\lvert H\rvert}$ であり、$[x^d]f_G=(-1)^{\sigma(D)}\bigl(\mathrm{EE}(D)-\mathrm{EO}(D)\bigr)$ を得る。$\square$
単純グラフ $G$ の向き付け $D$ で、頂点 $i$ の出次数を $d_i$ とする。$\mathrm{EE}(D)\neq\mathrm{EO}(D)$ なら、$G$ は $\ell(i):=d_i+1$ について $\ell$-選択可能である。
$f_G$ の全次数は辺の数 $\sum_id_i$ で、lem-cn-graph-polynomial により $x_1^{d_1}\cdots x_n^{d_n}$ の係数は $0$ でない（$\mathbb{Q}$ で考える）。大きさ $d_i+1$ のリスト $L_i\subset\mathbb{Q}$ について thm-cn-second を当てると $f_G(c)\neq0$ となる $c\in L_1\times\cdots\times L_n$ があり、これが求める彩色である。$\square$
長さ $2m$ の閉路を一方向に回るように向けると、各頂点の出次数は $1$ で、Euler 部分グラフは空集合と閉路全体（辺 $2m$ 本）の 2 つなので $\mathrm{EE}=2$、$\mathrm{EO}=0$ である。よって偶数長の閉路は 2-選択可能である。長さが奇数の閉路では同じ向き付けで $\mathrm{EE}=\mathrm{EO}=1$ となり定理は使えず、実際 2 色では塗れない。
完全二部グラフ $K_{3,3}$（頂点 $u_1,u_2,u_3$ と $v_1,v_2,v_3$）は 2 色で塗れるが 2-選択可能でない。$u_i$ と $v_i$ のリストを $\{1,2,3\}\setminus\{i\}$ とすると、3 つのリストに共通の色はないので $u_1,u_2,u_3$ には 2 色以上が使われ、$v_j$ はそれらをすべて避けなければならない。3 色が使われれば $v_j$ の色はなく、ちょうど 2 色 $\{1,2,3\}\setminus\{l\}$ なら $v_l$ のリストがそれに一致して色が残らない。
Alon と Tarsi は、平面グラフである 2 部グラフの選択数が $3$ 以下であることを、この定理とほかの組合せ論的な議論を合わせて導いた（Alo99 Theorem 7.4。この記事では証明しない）。
応用 5：イデアルによる特徴づけ
第 1 形は、組合せ論的な性質を「ある多項式がイデアルに入るか」で言い換える。
$G$ を頂点 $1,\dots,n$ の単純グラフ、$k\ge1$ とする。$G$ が $k$ 色で塗れない（隣り合う頂点の色が異なるように塗れない）ことと、$\mathbb{C}[x_1,\dots,x_n]$ で $f_G$ が $x_1^k-1,\dots,x_n^k-1$ の生成するイデアルに入ることは同値である。
$\mu_k$ を $1$ の $k$ 乗根全体とすると $x_i^k-1=\prod_{\zeta\in\mu_k}(x_i-\zeta)$ である。$k$ 色を $\mu_k$ の元と見ると、$G$ が $k$ 色で塗れないことは $f_G$ が $\mu_k^n$ の全点で $0$ になることと同じである。$f_G$ がイデアルに入れば $\mu_k^n$ で消える。逆に $\mu_k^n$ で消えれば、thm-cn-first（$S_i=\mu_k$）によりイデアルに入る。$\square$
これは Alo99 Theorem 9.3 で、同じ形で帯域幅や超グラフの 2 彩色の特徴づけも得られる（同 Proposition 9.4・9.5）。$k\ge3$ での $k$ 彩色の判定は NP完全 な問題なので、このような言い換えから効率のよい判定法がすぐ得られるわけではない。
補足
- 永久式の補題．体 $K$ 上の $n$ 次正方行列 $A=(a_{ij})$ の永久式 $\operatorname{per}A=\sum_{\sigma}\prod_ia_{i\sigma(i)}$ が $0$ でなければ、任意の $b\in K^n$ と 2 元集合 $S_1,\dots,S_n\subset K$ について、$x\in S_1\times\cdots\times S_n$ で $Ax$ の各成分が $b$ の成分と異なるものがある。$\prod_i\bigl(\sum_ja_{ij}x_j-b_i\bigr)$ の $x_1\cdots x_n$ の係数が $\operatorname{per}A$ なので、thm-cn-second からすぐ分かる（Alo99 Lemma 8.1）。
- 多項式法 との関係．多項式法の記事は、この定理を道具の 1 つとして、格子を超平面で覆う問題や有限体の掛谷集合などにも当てている。
- 構成的でないこと．第 2 形は値が $0$ でない点の存在を示すだけで、その点を効率よく見つける方法は与えない（Alo99 §10）。
関連項目
- 前提: 多項式環, 有限体, Lagrange補間
- 比較: Hilbertの零点定理, Schwartz–Zippelの補題, 多項式法
- 応用: Cauchy–Davenportの定理, Chevalley–Warningの定理, 五色定理, 正則グラフ
- 関連: Catalan数, Wilsonの定理
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
