發刊日期 |
2022年3月
|
---|---|
標題 | Alon的組合零點定理 |
作者 | |
關鍵字 | |
檔案下載 | |
全文 |
1. 從 Hilbert 的零點定理談起
本文主要在介紹 Noga Alon (以色列數學家, 1956 年 2 月 17 日生) 利用多項式解決組合問題的工作。
這要從David Hilbert (德國數學家, 1862 年 2 月 23 日 $\sim$ 1943 年 2 月 14 日) 的零點定理 (Nullstellensatz)說起,
它是代數幾何的一個基礎,
請參見 van der Waerden 的書 考慮以某個體 (field) $\mathbb{F}$ 為係數的所有 $n$ 個變數的多項式 $f=f(x_1,x_2,\ldots,x_n)$ 所成的集合, 其元素可做加、減、乘、除 (除法會產生商式和餘式), 是一個環 (ring), 稱之為多項式環 $\mathbb{F}[x_1,x_2,\ldots, x_n]$。 當 $c\ne 0$ 的時候, $f$ 的某一項 $c x_1^{d_1}x_2^{d_2}\ldots x_n^{d_n}$ 的度數 (degree) $deg(c x_1^{d_1}x_2^{d_2}\ldots x_n^{d_n})$ 定義成 $d_1+d_2+\cdots+d_n$, 而 $f$ 的度數則定義成 $f$ 當中度數最高的項的度數。 舉例來說, 在兩個變數的實係數多項式環 $\mathbb{R}[x,y]$ 中, $x^4 + 2 x^2 y^3 + 3 y^2$ 及其各項的度數為 $deg(x^4)=4$、 $deg(2x^2y^3)=5$、 $deg(3y^2)=2$、 $deg(x^4 + 2 x^2 y^3 + 3 y^2)=\max\{4,5,2\}=5$。 一個體 $\mathbb{F}$ 稱為代數封閉 (algebraically closed)的意思是說, $\mathbb{F}$ 中的任意不是常數的多項式一定有 $\mathbb{F}$ 中的根。 舉例來說, $\mathbb{R}$ 就不是代數封閉, 因為多項式 $x^2+1$ 沒有實數根。 但是 $\mathbb{C}$ 就是代數封閉, 因為根據代數基本定理, 任意不是常數的複係數多項式一定有一個複數根。 以下就是 Hilbert 的零點定理。 定理 1.1 (零點定理). 假設 $\mathbb{F}$ 是一個代數封閉體, $f, g_1, g_2, \ldots, g_m$ 是多項式環 $\mathbb{F}[x_1,x_2,\ldots$, $x_n]$ 中的一些多項式。 如果 $g_1, g_2, \ldots, g_m$ 的共同根也是 $f$ 的根, 則存在一個正整數 $k$ 及 $\mathbb{F}[x_1,x_2,\ldots,x_n]$ 中的一些多項式 $h_1, h_2, \ldots, h_m$, 使得 $f^k = h_1 g_1 + h_2 g_2 + \cdots + h_mg_m$。 對於 $m=n$ 而且各個 $g_i$ 是單變數多項式 $\prod_{a_i \in S_i} (x_i - a_i)$ 的特殊情況 (其中 $S_i$ 是 $\mathbb{F}$ 的有限非空子集), 有下面這個更強的定理。 值得注意的是, 這一次並不需要假設 $\mathbb{F}$ 有代數封閉的條件。 定理 1.2 假設 $\mathbb{F}$ 是一個體, $f = (x_1, x_2, \ldots, x_n)$ 是 $\mathbb{F}[x_1,x_2,\ldots,x_n]$ 中的一個多項式。 如果 $S_1, S_2, \ldots, S_n$ 是 $\mathbb{F}$ 的有限非空子集, 定義 $g_i(x_i) = \prod_{a_i\in S_i} (x_i - a_i)$。 如果 $g_1, g_2, \ldots, g_m$ 的共同根也是 $f$ 的根 (即對所有 $a_1\in S_1$、$a_2\in S_2$、$\ldots$、$a_n\in S_n$ 都有 $f(a_1, a_2, \ldots, a_n) = 0$), 則存在滿足 $deg(h_i) \le deg(f) - deg(g_i)$ 的多項式 $h_1, h_2, \ldots, h_n$ 使得 $f = h_1 g_1 + h_2 g_2 + \cdots + h_ng_n$。 更進一步來說, 當 $R$ 是 $\mathbb{F}$ 的子環, 而且 $f, g_1, g_2, \ldots, g_n$ 都在 $R[x_1, x_2, \ldots, x_n]$ 時, 前述的 $h_i$ 也都在 $R[x_1, x_2, \ldots, x_n]$ 內。
Alon 定理 1.3 組合零點定理. 假設某個體 $\mathbb{F}$ 中有 $n$ 個子集 $S_1,S_2,\ldots,S_n$, 每一個都滿足 $|S_i| \gt d_i$; 而且 $f$ 是 $\mathbb{F}[x_1,x_2,\ldots,x_n]$ 中的一個多項式。 如果 $f$ 的度數為 $d_1+d_2+\cdots+d_n$, 而且它有某個非零項 $c x_1^{d_1} x_2^{d_2} \cdots x_n^{d_n}$, 則存在 $a_1\!\in\! S_1$、$a_2\!\in\! S_2$、$\ldots$、$a_n\!\in\! S_n$ 使得 $f(a_1,a_2,\ldots,a_n) \!\ne\! 0$。
對於組合零點定理的證明,
Alon (C1) $f$ 的度數為 $d_1+d_2+\cdots+d_n$, 而且它有某個非零項 $c x_1^{d_1} x_2^{d_2} \ldots x_n^{d_n}$, 換成一個比較強的假設 (C0) $f\not\equiv 0$, 而且它的任意非零項 $c x_1^{d_1'} x_2^{d_2'} \ldots x_n^{d_n'}$ 均滿足 $d_1'\le d_1, d_2'\le d_2, \ldots, d_n'\le d_n$。
Alon 先證明了弱組合零點定理,
用它來證明定理 1.2,
然後再用定理 1.2 來證明組合零點定理。
Tao 和 Vu (C2) $f$ 有某個非零項 $c x_1^{d_1} x_2^{d_2} \ldots x_n^{d_n}$, 且對 $f$ 中任意非零項 $c' x_1^{d_1'} x_2^{d_2'} \ldots x_n^{d_n'}$, 若所有 $d_i' \ge d_i$ 則所有 $d_i' = d_i$。 顯然 (C0) 可推得 (C1), 而 (C1) 可以推得 (C2), 但是反過來都不成立。 例如, 當 $d_1=2$、$d_2=3$、$d_3=4$ 時, $x_1^2 x_2^3 x_3^4 + x_1^2 x_2^2 x_3^5$ 滿足 (C1) 但不滿足 (C0), $x_1^2 x_2^3 x_3^4 + x_1^2 x_2^2 x_3^6$ 滿足 (C2) 但不滿足 (C1)。 證明強組合零點定理: 對 $d:=d_1+d_2+\cdots+d_n$ 做數學歸納法證明。 當 $d=0$ 的時候 $d_1=d_2=\ldots=d_n=0$, $f$ 為非零常數多項式, 定理顯然成立。 假設 $d\ge 1$, 不妨假設 $d_1\ge 1$。 選取 $a\in S_1$, 利用多項式的長除法, 將 $f$ 除以 $x_1-a$ 可得 $$ f(x_1,x_2,\ldots,x_n) = q(x_1,x_2,\ldots,x_n) (x_1-a)+ r(x_2,x_3,\ldots,x_n), $$ 由於 $f$ 滿足條件 (C2), 可知 $q(x_1,x_2,\ldots, %某個非零 x_n)$ 有一項 $c x_1^{d_1-1} x_2^{d_2} \ldots x_n^{d_n}$ 滿足條件 (C2) (但其中的 $d_1$ 換成 $d_1-1$)、 $r(x_2,x_3,\ldots,x_n)$ 是一個有 $n-1$ 個變數的多項式。 根據已知條件, $\mathbb{F}$ 的子集 $S_1\backslash\{a\},S_2,\ldots,S_n$ 除了 $|S_1\backslash\{a\}| \gt d_1-1$ 外都有 $|S_i| \gt d_i$ ; 由歸納法假設, 存在$a_1\in S_1\backslash\{a\}$、$a_2\in S_2$、$\ldots$、$a_n\in S_n$ 使得 $q(a_1,a_2,\ldots,a_n) \ne 0$。 如果 $r(a_2,a_3,\ldots,a_n)=0$, 則 $f(a_1,a_2,\ldots,a_n)=q(a_1,a_2,\ldots,a_n)(a_1-a) \ne 0$; 如果 $r(a_2,a_3,\ldots,a_n)\ne 0$, 則 $f(a,a_2,\ldots,a_n)=r(a_2,a_3,,\ldots,a_n) \ne 0$。 定理得證。 $\Box$
接下來我們要利用組合零點定理來解決一些組合問題,
其用法就是設法造出一個多項式 $f(x_1,x_2,\ldots,x_n)$ 來模擬想要證明命題的特性,
使得如果這個多項式存在一個特定的點 $(a_1$, $a_2,\ldots,a_n)$ 滿足 $f(a_1,a_2,\ldots,a_n) \ne 0$ 的話,
$(a_1,a_2,\ldots,a_n)$ 就會對應於想要的東西,
然後再用組合零點定理來證明這樣的 $(a_1,a_2,\ldots,a_n)$ 的確存在。
這些及更多的內容請參見 Alon 的文章 2. Cauchy-Davenport 定理 --- 加性數論在數論中, 加性數論 (additive number theory)在研究整數的子集合, 以及其在加法下的特性。 更抽象來說, 加性數論的研究包括對於有加法運算的交換群 (abelian group)以及交換半群 (commutative semigroup)。 其中主要研究的二個對象分別是交換群或半交換群 $G$ 中二個子集 $A$ 及 $B$ 的和集 (sumset) $$ A+B = \{a+b: a\in A,b\in B\}, $$ 以及 $A$ 的 $k$-重和集 ($k$-fold sumset) $$ k A = \underbrace{A + A + \cdots + A}_k\mbox{。} $$
在這方面的研究,
有一個方向是直接問題,
也就是由 $A$ 的結構來判斷 $kA$ 的結構。
例如,
假設 $A$ 是一個固定的子集,
判斷哪些元集可以表示為 $kA$ 中的和元素 (參見 許多這一類的研究常使用 Hardy-Littlewood 圓法 (circle method)及篩法 (sieve methods)當工具。 例如 Vinogradov 證明了, 每一個夠大的奇數都可以表示為三個質數的和, 以及所有夠大的偶數都可以表示為四個質數的和。 Hilbert 證明了, 對於每一個正整數 $n$, 每一個非負整數都是某一個固定數目 $k$ 的 $n$ 次方數的和, 也就是 $k A_n$ 包含了所有正整數; 例如 $n=2$ 時, 每一個非負整數都是 4 個 2 次方數的和, 也就是 $4 A_2$ 包含了所有正整數。 一般來說, 對於某個非負整數的子集 $A$, 若可以讓 $kA$ 包括所有的正整數, $A$ 就稱為 $k$ 階的基底 (basis of order $k$); 若 $kA$ 包括所有夠大的整數, $A$ 就稱為 $k$ 階漸近基底 (asymptotic basis of order $k$)。 最近有許多研究是關於有限階漸近基底的一般特性, 例如, 若集合 $A$ 是 $k$ 階漸近基底, 但集合 $A$ 的真子集都不是 $k$ 階漸近基底, 則集合 $A$ 稱為 $k$ 階的最小漸近基底 (minimal asymptotic basis of order $k$)。 目前已經證明了, 對於任意 $k$, 總是存在 $k$ 階的最小漸近基底, 但是也存在不包含$k$ 階的最小漸近基底的$k$ 階漸近基底。 另一個問題是, 一個 $n$ 最少可以表示成某個最小漸進基底中多少個元素的和。 著名的 Erdős–Turán 猜想也是有關漸近基底的問題。
另一個方向關注的是反問題 (最近此研究方向常稱為加性組合學),
假設已經知道和集 $A+B$ 的資訊,
目的是要找到個別集合 $A$ 和 $B$ 的資訊 (參見 下面來介紹 Cauchy-Davenport 定理。 先介紹一些更基礎的內容。 假設 $A$ 和 $B$ 是兩個正整數的有限非空子集, 令 $|A|= n$ 而 $|B| = m$。 第一個問題是, $|A+B|$ 可能會多大? 當 $A=\{1,2,\ldots, n\}$ 而 $B = \{n,2n,\ldots,mn\}$ 時, $A+B=\{n+1,n+2,\ldots, n+mn\}$, 此時 $|A+B|=mn=|A| |B|$, 相對比較大。 事實上, 這已經是最大可能了, 因為容易看出來, 一般來說都有 $$ |A+B| \le |A| |B|\mbox{。} $$ 另一方面, 當 $A=\{1,2,\ldots, n\}$ 而 $B = \{1,2,\ldots,m\}$ 時, $A+B=\{2,3,\ldots, n+m\}$, 此時 $|A+B|=n+m-1=|A|+|B|-1$, 相對比較小。 事實上, 這是最小可能了, 一般來說, 假設 $$ A = \{a_1 \lt a_2 \lt \cdots \lt a_n\} \mbox{、} \quad B = \{b_1 \lt b_2 \lt \cdots \lt b_m\}, $$ 則下面這個遞增數列包含了 $A+B$ 中的 $n+m-1$ 個數, $$ a_1\!+\!b_1 \!\lt\! a_1\!+\!b_2 \!\lt\! a_1\!+\!b_3 \!\lt\! \cdots \!\lt\! a_1\!+\!b_{m-1} \!\lt\! a_1\!+\!b_m \!\lt\! a_2\!+\!b_m \!\lt\! \cdots \!\lt\! a_{n-1}\!+\!b_m \!\lt\! a_n\!+\!b_m\mbox{。} $$ 反過來, 我們可以問, 如果 $|A+B|=|A|+|B|-1$, 那麼 $A$ 和 $B$ 會長成甚麼樣子? 當 $A$ 或 $B$ 只有一個元素時, 不管另一個集合長相如何, 顯然會有 $|A+B|=|A|+|B|-1$。 所以假設 $|A|=n\ge 2$ 且 $|B|=m\ge 2$。 當 $|A+B|=n+m-1$ 時, 再考慮下面這個遞增數列, 它也包含了 $A+B$ 中的 $n+m-1$ 個數, $$ a_1\!+\!b_1 \!\lt\! a_2\!+\!b_1 \!\lt\! a_2\!+\!b_2 \!\lt\! \cdots \!\lt\! a_2\!+\!b_{m-2} \!\lt\! a_2\!+\!b_{m-1} \!\lt\! a_3\!+\!b_{m-1} \!\lt\! \cdots \!\lt\! a_n\!+\!b_{m-1} \!\lt\! a_n\!+\!b_m\mbox{。} $$ 因為 $|A+B|=n+m-1$, 前述的兩個數列, $A+B$ 的所有元素恰好都出現在數列中一次, 所以這兩個數列的各對應項相等, 而有 $$ a_1+b_j = a_2+b_{j-1} \ (2\le j\le m) \mbox{、} a_i+b_m = a_{i+1}+b_{m-1} \ (1\le i\le n-1), $$ 也就是 $$ a_2-a_1 = b_j-b_{j-1} \ (2\le j\le m) \mbox{、} a_{i+1}-a_i = b_m - b_{m-1} \ (1\le i\le n-1), $$ 因此, $A$ 和 $B$ 是兩個有共同非零公差 $d$ 的等差級數所成的集合。 當然, 具有這樣性質的 $A$ 和 $B$ 也會有 $|A+B|=|A|+|B|-1$。 綜合來說, 有如下的性質。 命題 2.4 若 $A$ 和 $B$ 是 $\mathbb{Z}$ 的有限非空子集, 則 $|A+B| \ge |A|+|B|-1$。 更進一步來說, $|A+B| = |A|+|B|-1$ 若且唯若 $|A|=1$ 或 $|B|=1$, 或是存在某個 $d \gt 0$ 使得 $$ A = \{a, a+d, a+2d, \ldots, a+(|A|-1)d\} \mbox{、} B = \{b, b+d, b+2d, \ldots, b+(|B|-1)d\}\mbox{。} $$ 性質 2.4 的證明主要用到整數可以比較大小, 所以將其中的整數集 $\mathbb{Z}$ 換成實數集 $\mathbb{R}$, 性質還會成立。 但是如果將整數集 $\mathbb{Z}$ 換成複數集 $\mathbb{C}$, 情況會是如何呢? 一般常說, 複數集是「不能定義」大小關係的; 這樣的說法其實不夠精確, 更精確來說, 應該是, 如果在複數集定義大小關係, 則不能滿足一般大小關係習慣有的一些性質, 例如
(P1) 三個關係 $a \lt b$、 $a=b$、 $b \lt a$ 恰有一個成立; 如果複數中可以定義滿足前述五個性質的大小關係, 則會產生矛盾, 說明如下。 先來看 $\sqrt{-1}$。 因為 $0 \ne\sqrt{-1}$, 則由 (P1) 可知 $0\lt\sqrt{-1}$ 或 $\sqrt{-1}\lt0$。 當 $0\lt\sqrt{-1}$ 時, 由 (P5) 就會得到 $0 \sqrt{-1} \lt \sqrt{-1}\sqrt{-1}$, 也就是 $0\lt-1$。 當 $\sqrt{-1}\lt0$ 時, 由 (P2) 就有 $0\lt-\sqrt{-1}$, 再由 (P5) 就會得到 $0(-\sqrt{-1}) \lt (-\sqrt{-1})(-\sqrt{-1})$, 也就是 $0\lt-1$。 所以總是有 $0\lt-1$, 再一次利用 (P5) 得到 $0(-1)\lt(-1)(-1)$, 也就是 $0\lt1$, 再由 (P2) 就有 $-1\lt0$, 這和 $0\lt-1$ 違反 (P1) 而產生矛盾。 不過, 複數中卻可以定義大小關係為 $$ \mbox{「對於實數 $a, b, a', b'$, 若 $a \lt a'$、或者 $a=a'$ 但是 $b \lt b'$, 則稱 $a+b\sqrt{-1} \lt a'+b'\sqrt{-1}$。」} $$ 此時雖然性質 (P5) 不成立, 但是 (P1)、(P2)、(P3)、(P4) 都成立。 前面證明性質 2.4 時, 其實並不會用到乘法, 只需有性質 (P1)、(P2)、(P3)、(P4) 就夠了。 所以性質 2.4 中的 $\mathbb{Z}$ 換成 $\mathbb{C}$ 後還是成立。 這樣來說, 是不是對任何加法系統都會有 $|A+B|\ge|A|+|B|-1$ 的不等式? 答案是不會。 考慮模環 $\mathbb{Z}_r$, 也就是 $\mathbb{Z}_r=\{0,1,2,\ldots,r-1\}$, 其中的加法、乘法是整數的加法、乘法後取 mod $r$。 例如, 在 $\mathbb{Z}_9$ 中, $3+3=6$、$6+6=(12 {\rm\ mod\ } 9)=3$、$2\times 2=4$、$4\times 4=(16 {\rm\ mod\ } 9)=7$。 要注意的是, 為了討論性質 2.4 並不需要考慮乘法。 其次, $\mathbb{Z}_r$ 中並無法定義大小關係使得性質 (P1)、(P3)、(P4) 都成立, 說明如下。 如果 $0\lt1$, 則連續使用 (P4) 就會得到 $1\lt2$、$2\lt3$、$\ldots$、$n-1\lt(n-1)+1=0$, 再連續使用 (P3) 就會得到 $0\lt0$, 和 (P1) 矛盾; 如果 $1 \lt 0$, 則連續使用 (P4) 就會得到 $2\lt1$、$3\lt2$、$\ldots$、$0=(n-1)+1 \lt n-1$, 再連續使用 (P3) 就會得到 $0 \lt 0$, 和 (P1) 矛盾。 事實上, 考慮 $\mathbb{Z}_9$ 的部分集合 $A=B=\{0,3,6\}$ 時, $A+B=\{0,3,6\}$, 所以 $|A+B|=|A|=|B|=3$, 此時 $|A+B|\ge |A|+|B|-1$ 並不成立。 不過在特殊情況, 當 $r$ 是質數時, 只要 $|A+B|$ 不超過 $r$, 確實會有 $|A+B|\ge |A|+|B|-1$, 這就是著名的 Cauchy-Davenport 定理。 定理 2.5 (Cauchy-Davenport 定理). 若 $p$ 為質數, $A$ 和 $B$ 為 $\mathbb{Z}_p$ 的兩個非空子集 , 則 $|A+B| \ge \min\{p, |A|+|B|-1\}$。
Augustin-Louis Cauchy (法國數學家, 1789 年 8 月 21 日 $\sim$ 1857 年 5 月 23 日) 在 1813 年證明了這個定理,
利用它重新證明了 Joseph-Louis Lagrange (義大利數學家, 1736 年 2 月 25 日 $\sim$ 1813 年 4 月 10 日) 在 1770 年得到的結果,
任意正整數是 4 個平方數的和。
後來 Davenport 將此定理敘述為 Khintchine 的一個關於兩個整數列和的 Schnirelman 密度的猜想 (後來被 H. Mann 證明了) 的離散相似版本,
這個結果有若干推廣,
例如可參見 證明 Cauchy-Davenport 定理: 如果 $|A+B|\ge p$, 定理顯然成立, 所以只需考慮 $|A+B|\le p-1$ 的情況。 假設定理不成立, 也就是 $|A+B|\le |A|+|B|-2$。 令 $S_1=A$ 且 $S_2=B$, 則可選取非負整數 $d_1$ 和 $d_2$ 使得 $|A+B|=d_1+d_2$、 $|S_1| \gt d_1$、 $|S_2| \gt d_2$。 考慮 $\mathbb{Z}_p[x,y]$ 中的多項式 $$ f(x,y) = \prod_{c\in A+B} (x+y-c), $$ 其度數為 $|A+B|=d_1+d_2$, 而且它有一個項 ${d_1+d_2 \choose d_1} x^{d_1} y^{d_2}$。 因為 $d_1+d_2 \lt p$, 所以 ${d_1+d_2 \choose d_1}$ 當作整數不是 $p$ 的倍數, 當作 $\mathbb{Z}_p$ 的元素不為 0, 所以根據組合零點定理, 存在 $a\in A$、$b\in B$ 使得 $f(a,b)\ne 0$。 因為 $a+b\in A+B$, 由 $f(x,y)$ 的定義得知 $f(a,b)=0$, 矛盾。 $\Box$ 一些涉及限制和集的類似結果如下所述。
定理 2.6. (Dias da Silva-Hamidoune
定理 2.7. (Alon-Nathanson-Ruzsa 3. 利用組合零點定理證明圖論中的三個定理
圖論這門學問有將近三百年的歷史,
經由各方學者的研究,
已經有很完整的發展,
不但在數學上有其深度,
在其他領域上也有很多應用。
很少有一個數學的分支可以說是哪一年誕生的,
而現在大家公認,
Euler 在 1736 年解決 Königsberg 七橋問題的文章
從 1736 年到 1936 年這整整兩百年,
可以說是圖論的春秋戰國時代,
不同領域的人們在他們各自的崗位上,
用不同的名稱、不同的內容,
探索和 Euler 發現的圖一樣的概念 (參見 Biggs、 Lloyd 和 Wilson 的書 這一節利用組合零點定理來證明一些圖論上的定理。 我們討論的圖都是簡單圖 (simple graph), 也就是, 只有有限多個點、 沒有重邊 (multiple edges)、 沒有迴邊 (loops); 如果要討論有有限多個點、 允許重邊、 沒有迴邊的圖, 會稱之為重圖 (multi-graph)以便區別。 正則子圖的存在性
Berge 和 Sauer 曾猜想任何 4-正則圖都一定包含一個 3-正則子圖 (參見 Bondy 和 Murty 的書
定理 3.1 (Alon-Friedland-Kalai 證明: 假設 $G$ 有 $n$ 點及 $m$ 邊。 每一條邊 $e$ 定義一個變數 $x_e$, 然後考慮在有限體 $\mathbb{Z}_p$ 上的多項式 $$ f(\vec{x}) = \prod_{v\in V(G)} \bigg(1 - \Big(\sum_{e\ni v} x_e \Big)^{p-1} \bigg) - \prod_{e\in E(G)} \left(1- x_e\right)\mbox{。} $$ 這個多項式第一個乘積是把 $n$ 個度數是 $p-1$ 的多項式乘起來, 而因為 $G$ 的平均度數大於 $2p-2$, 知道有 $n(p-1) \lt m$; 又因為它的第二個乘積的度數是 $m$, 於是知道 $f(\vec{x})$ 的度數是 $m$, 其中 $\prod_{e\in E(G)} x_e$ 這項的係數是 $(-1)^{m+1}$, 所以不等於 0。 對於這項來說每個 $d_e$ 都是 1, 所以若對所有 $e \in E$ 都取 $S_e = \{0,1\}$, 則根據組合零點定理, 存在某個 $\vec{a}=(a_e: e\in E(G))\in\prod_{e\in E(G)} S_e$ 使得 $f(\vec{a})\ne 0$。 這時候, 根據各個 $a_e$ 是 0 或 1, 可以決定出 $G$ 的一個子重圖 $H$, 其中 $e \in E(H)$ 若且唯若 $a_e = 1$。 這個子重圖 $H$ 至少有一條邊, 因為 $f(\vec{0})=0$。 既然 $H$ 有邊, 那麼在 $f(\vec{a})$ 的定義當中第二個乘積就會是 0。 這時候, 如果對於某個 $v$ 來說 $\sum_{e\ni v} a_e$ 在 $\mathbb{Z}_p$ 當中不是 0, 那麼根據 Fermat 小定理就有 $$ 1 - \Big(\sum_{e\ni v} a_e \Big)^{p-1} \equiv 0 {\rm ~(mod~} p), $$ 所以 $f(\vec{a})$ 的定義當中的第一個乘積也是 0, 這跟 $f(\vec{a})\ne 0$ 矛盾; 這就表示對於每個點 $v$ 來說都要有 $deg_H(v) = \sum_{e\ni v} a_e \equiv 0$ (mod $p)$, 但問題是 $\Delta(G) = 2p-1$, 所以 $deg_H(v)$ 若不是 0 就是恰好等於 $p$, 所以 $H$ 去掉那些孤立點以後就是 $G$ 的一個 $p$-正則子重圖。 $\Box$ 和 d-點團集相交的集合的數目下面是組合零點定理的另一個應用, 其內容看起來有一點不自然, 但展示了組合零點定理的多功能性。 定理 3.2. 如果 $p$ 是質數, 而 $G=(V,E)$ 的點數 $|V| \gt d(p-1)$, 則存在一個非空的點集 $U\subseteq V$, 使得和 $U$ 相交的 $d$-點團的數目是 $p$ 的倍數。 證明: 每一個點 $v$ 定義一個變數 $x_v$, 然後考慮在有限體 $\mathbb{Z}_p$ 上的多項式 $$ f(\vec{x}) = \prod_{v\in V} (1-x_v) - 1 + g(\vec{x})^{p-1}\mbox{, 其中~} g(\vec{x}) = \sum_{\emptyset\ne I\subseteq V} (-1)^{|I|+1}K(I)\prod_{v\in I} x_v, $$ $K(I)$ 表示包含 $I$ 的 $d$-點團的數目。 因為只有在 $|I|\le d$ 的時候 $K(I)\ne 0$, 所以 $g(\vec{x})$ 的次數最多是 $d$; 又因為 $|V| \gt d(p-1)$, 所以 $f(\vec{x})$ 的次數是 $|V|$, 其中 $\prod_{v\in V} x_v$ 這項的係數是 $(-1)^{|V|}$, 所以不等於 0。 對於這項來說每個 $d_v$ 都是 1, 所以如果對所有 $v \in V$ 都取 $S_v = \{0,1\}$, 則根據組合零點定理, 存在某個 $\vec{a}=(a_v: v\in V)\in\prod_{v\in V} S_v$ 使得 $f(\vec{a})\ne 0$。 令 $U=\{v\in V: a_v=1\}$, 因為 $f(\vec{0})=0$, 所以 $U\ne\emptyset$。 既然 $U\ne\emptyset$, 那麼在 $f(\vec{a})$ 的定義當中第一個乘積就會是 0。 這時候, $g(\vec{a})^{p-1}\ne 1$, 那麼根據 Fermat 小定理就有 $g(\vec{a})=0 \in \mathbb{Z}_p$, 因為 $\prod_{v\in I} a_v$ 只有在 $I\subseteq U$ 的時候不是 0, 其實等於 1, 所以 $g(\vec{a})=\sum_{\emptyset\ne I\subseteq U} (-1)^{|I|+1}K(I)$, 根據排容原理, 這就是和 $U$ 相交的 $d$-點團的個數, 在 $\mathbb{Z}_p$ 是 0, 當作整數是 $p$ 的倍數。 $\Box$
上面這個結果也可以推廣到 $p$ 是某個質數的次方的情況,
一些相關的結果請參見 圖著色問題
圖的著色問題可追溯到 1850 年英國有一位學生 Francis Guthrie 提出來的四色問題。
這個問題經過一百多年,
最後才在 1976 年,
由 Appel, Haken 與 Koch 四色問題可以說是圖論當中, 除了七橋問題以外最有名的問題, 其所衍生出來的許多著色問題, 引發了許多精彩的理論。 著色問題除了歷史性的挑戰以外, 在現今的許多實際應用問題如: 排時、 排序、 時間表、 頻道分配、 資源分配、 實驗設計等議題上都十分有用。 圖著色與圖論的其他部分、 數學的其他分支, 甚至其他科學也有很深而不可分離的關係。 一百多年來的發展, 已經產生了許多深刻的結果與工具, 並且造就了許多具挑戰性的未解問題。 一個圖 $G$ 的 $k$-著色 ($k$-coloring) 是指一個函數 $f:V(G) \to \{1,2,\ldots,k\}$, 而一個正常 $k$-著色 (proper $k$-coloring)則是指使得 $f(x) \ne f(y)$ 對相鄰兩點 $x$ 和 $y$ 都成立的 $k$-著色。 圖 $G$ 的著色數 (chromatic number)$\chi(G)$ 是指使得 $G$ 存在正常 $k$-著色的最小 $k$。 如果 $\chi(G) \le k$, 也會說 $G$ 可以被 $k$-著色 ($k$-colorable)。 在這個定義之下, 四色定理的內容就是「任意平面圖 $G$ 都可以被四著色」。
列表著色是點著色的一種推廣,
在這種著色方式當中仍舊是要給每一點著上一種顏色,
不過每個點各自可以使用的顏色集合可能各不相同,
有別於先前的著色模式中每個點可用的顏色集合都是 $\{1,2,\ldots,k\}$。
這種著色概念由 Vizing 對於圖 $G$ 中的每一點 $v$, 令 $L(v)$ 是可供 $v$ 選擇的顏色集。 一個正常列表著色 (proper list coloring)$f$ 是使得每一點 $v$ 都有 $f(v) \in L(v)$ 的正常著色。 如果無論 $L(v)$ 如何給定, 只要 $|{L(v)}| \ge k$ 的話 $G$ 都有正常列表著色, 就說 $G$ 可被列表 $k$-著色 (list $k$-colorable) 或 $k$-可選擇的 ($k$-choosable), 而 $G$ 的列表著色數 (list chromatic number 或 choice number 或 choosability) $\chi_\ell(G)$ 就是使 $G$ 可被列表 $k$-著色的最小 $k$。
Alon 對於有 $n$ 個點的圖 $G=(V,E)$, 不妨假設 $V=\{1,2,\ldots,n\}$, 點 $i$ 對應到變數 $x_i$, 考慮 $n$ 個變數的 $|E|$ 次多項式 $$ f_G(x_1,x_2,\ldots,x_n)=\prod\{(x_i-x_j): i \lt j, \{i,j\} \in E\}\mbox{。} $$ 說一個有向圖 $D$ 是一個循環 (circulation), 如果 $deg_D^+(v) = deg_D^-(v)$ 對於每個點 $v$ 都成立的話。 一個循環的奇偶性是根據它邊數的奇偶性來界定的。 用 $CE(D)$ 和 $CO(D)$ 分別表示, 有向圖 $D$ 的子圖是偶循環和奇循環的集合。
定理 3.3 (Alon-Tarsi 證明: 對 $1\le i\le n$, 令 $S_i \subseteq \mathbb{Z}$ 含 $d_i+1$ 個整數, 要由 $S_i$ 中取一個顏色 $a_i$ 著點 $i$ 構成 $G$ 的著色, 等同於要滿足 $f_G(a_1,a_2,\ldots,a_n)\ne 0$。 因為 $f_G(x_1,x_2,\ldots,x_n)$ 的度數是 $\sum_{i=1}^n d_i$, 由組合零點定理, 只要驗證 $\prod_{i=1}^n x_i^{d_i}$ 在 $f_G$ 的係數不是 0 就可以。 把 $f_G(x_1,x_2,\ldots,x_n)$ 的 $|E|$ 個相乘項 $x_i-x_j$ 展開, 得到 $2^{|E|}$ 項 $(-1)^r \prod_{i=1}^n x_i^{d_i'}$, 這種單項多項式對應到 $G$ 的一個定向 $D'$: 從 $|E|-r$ 項 $x_i-x_j$ 中取 $x_i$ 相乘、 這對應到有向邊 $ij$, 從 $r$ 項 $x_i-x_j$ 中取 $-x_j$ 相乘, 這對應到有向邊 $ji$。 這時候, 對所有 $i$ 會有 $d_i'=deg_{D'}^+(i)$。 用 $DE(d_1',d_2',\ldots,d_n')$ 和 $DO(d_1',d_2',\ldots,d_n')$ 分別表示 $G$ 的定向 $D'$ 出度序列是 $d_1',d_2',\ldots,d_n'$ 而 $r$ (也就是 $j \gt i$ 的邊 $ji$ 的個數)是偶數和奇數的集合, 則 $$ f_G(x_1,x_2,\ldots,x_n) =\sum_{d_1',d_2',\ldots,d_n'\ge 0} \left(|DE(d_1',d_2',\ldots,d_n')|-|DO(d_1',d_2',\ldots,d_n')|\right) \prod_{i=1}^n x_i^{d_i'}\mbox{。} $$ 對給定的 $D$, 它的度序列是 $d_1,d_2,\ldots,d_n$。 對任意 $D'\in DE(d_1,d_2,\ldots,d_n) \cup DO(d_1$, $d_2,\ldots,d_n)$, 考慮 $D$ 中在 $D'$ 中是反向的所有邊的集合 所構成的有向圖 $D''$。 因為 $D$ 和 $D'$ 有相同的出度序列, 所以 $D''$ 是 $D$ 的循環子圖。 對應 $D' \longrightarrow D''$ 顯然是 $DE(d_1,d_2,\ldots,d_n) \cup DO(d_1,d_2,\ldots,d_n)$ 到 $CE(D)\cup CO(D)$ 的 1-1 映成函數, 而且當 $D \in DE(d_1,d_2,\ldots,d_n)$ 的時候 $D' \in DE(d_1,d_2,\ldots,d_n)$ 若且唯若 $D''\in CE(D)$, 當 $D \in DO(d_1,d_2,\ldots,d_n)$ 的時候 $D' \in DE(d_1,d_2,\ldots,d_n)$ 若且唯若 $D''\in CO(D)$, 所以 $$ \left| |DE(d_1,d_2,\ldots,d_n)|-|DO(d_1,d_2,\ldots,d_n)| \right| =\left| |CE(D)|-|CO(D)| \right| , $$ 由於 $|CE(D)| \ne |CO(D)|$, 得知 $|DE(d_1,d_2,\ldots,d_n)|-|DO(d_1,d_2,\ldots,d_n)| \ne 0$, 也就是 $\prod_{i=1}^n x_i^{d_i}$ 在 $f_G$ 的係數不是 0。
最後來討論這個定理的一個有趣的應用。
堵丁柱、許得標、黃光明 參考文獻---本文作者任台灣大學數學系, 名譽教授--- |