數學傳播

在高中數學競賽 (Mathematical Competitions of High School Students) 中, 往往會遇到棋盤染色問題。請看以下數例。

例1:(1976年美國數學競賽(27th Mathematical Competitions of American High School Students) 試題) 用黑白二種顏色去染一個 $4\times 7$ 棋盤上的每個方格, 每個方格染而且只染一種顏色。證明,不論如何染色, $4\times 7$ 棋盤上一定有一個由方格組成的矩形, 它的四個角上的方格顏色相同, 而對於一個 $4\times 6$ 棋盤,一定有一種染色方式,使得棋盤上每一個由方格組成的矩形, 它的四個角上的方格不全同色。

例2:(1983年瑞士數學競賽(Mathematical Competitions of Swiss High School Students) 試題) 用紅、黃、藍三種顏色去染一個 $12\times 12$ 棋盤上的每個方格, 每個方格染而且只染一種顏色。證明,不論如何染色, $12\times 12$ 棋盤上一定有一個由方格組成的矩形,它的四個角上的方格顏色相同。

例3: (1985年國際數學奧林匹克(26th International Mathematical Olympiad) 備選題) 用 $n$ 種顏色 $c_1,c_2,\ldots$, $c_n$ 去染格點集合 $M\!=\!\{ (x,y)|x\!=\!0,1,\cdots ,kn-1$, $y=0,1,\cdots,\ell n-1\}$ 中的格點, 每個格點染而且只染一種顏色。如果對於每種顏色 $c_i$, 格點集合 $M$ 中每一行上都恰有 $k$ 個 $c_i$ 色格點,每一列上都恰有 $\ell$ 個 $c_i$ 色格點, 而且對於格點集合 $M$ 中每個以格點為頂點的矩形,它的四個頂點的顏色都不全相同, 則這樣的染色方式 $f$ 稱為允許的。證明,如果對於格點集合 $M$, 允許的染色方式 $f$ 存在,則 $k\ell\le n(n+1)$。

以上都是棋盤染色問題的特殊情形。設 $M$ 是一個 $m\times n$ 棋盤, $c_1,c_2,\cdots,c_k$ 是 $k$ 種不同顏色。用顏色 $c_1,c_2,\cdots,c_k$ 去染棋盤 $M$ 上的方格,每個方格染而且只染一種顏色,得到的棋盤稱為 $k$ 色棋盤, 仍記作 $M$。當然,由於染色方式的不同,得到的 $k$ 色棋盤 $M$ 也不同。 設 $M$ 是一個 $k$ 色棋盤。如果 $k$ 色棋盤 $M$ 上由方格組成的矩形 $D$ 的四個角上的方格顏色相同,則矩形 $D$ 稱為單色矩形,否則稱為雜色矩形。

例如圖一所示的2色 $4\times 4$ 棋盤 $M$ 含有單色矩形 $D$ , 而圖二所示的2色 $4\times 4$ 棋盤 $M$ 不含單色矩形。於是用 $k$ 色棋盤和單色矩形的語言,例1可以改述為:證明,任意一個2色 $4\times 7$ 棋盤一定含有單色矩形,而且存在不含單色矩形的2色 $4\times 6$ 棋盤; 例2則是要證明,任意一個 3 色 $12\times 12$ 棋盤總含有單色矩形。 至於例3,則可考慮一個 $kn\times \ell n$ 棋盤 $M^*$ , 其第 $i$ 列和第 $j$ 行的交叉位置上的方格標以坐標 $(i-1,j-1),i=1,2,\cdots,kn$, $j=1,2,\cdots,\ell n$,則方格 $(i-1,j-1)$ 便在直角坐標平面上確定一個格點 $(i-1,j-1)$, 所有格點的集合即是給定的格點集合 $M$ 。設 $f$ 是格點集合 $M$ 的用 $n$ 種顏色 $c_1,c_2,\cdots,c_n$ 去染格點的一種染色方式,而且設格點 $(i-1,j-1)$ 在染色方式 $f$ 下染成 $c_k$ 色,我們將棋盤 $M^*$ 上第 $i$ 列和第 $j$ 行相交叉的方格染成 $c_k$ 色,便得到 $M^*$ 的一種染色。容易看出, 格點集合 $M$ 的一種允許的染色方式 $f$ 便確定 $kn\times \ell n$ 棋盤 $M^*$ 的這樣一種染色方式,使得棋盤 $M^*$ 的每一列上 $c_i$ 色方格的個數為 $k$, 每一行上 $c_i$ 色方格的個數為 $\ell,i=1,2,\cdots,n$, 而且 $n$ 色棋盤 $M^*$ 不含單色矩形。於是例3即是要證明,如果這樣的 $n$ 色 $kn\times \ell n$ 棋盤 $M^*$ 存在,則 $k\ell\le n(n+1)$。

關於 $k$ 色棋盤 $M$,主要關心的問題是: 1.對於給定的 $k$,參數 $m$ 和 $n$ 滿足怎樣的條件,才能使得任意一個 $k$ 色 $m\times n$ 棋盤 $M$ 一定含有單色矩形。其對偶形式是,對於給定的 $k$, 參數 $m$ 和 $n$ 滿足怎樣的條件,才能保證一定存在一個不含單色矩形的 $k$ 色 $m\times n$ 棋盤?

2.對於給定的 $k$,求這樣的最小正整數 $L(k)$,使得當 $n\ge L(k)$ 時, 任意一個 $k$ 色 $n\times n$ 棋盤 $M$ 一定含單色矩形。 數 $L(k)$ 稱為棋盤Ramsey數,確定棋盤Ramsey數 $L(k)$ 是棋盤染色的一基本問題。 它和組合數學中的Ramsey理論有著密切的聯繫。 這裡將簡要介紹處理棋盤染色問題的一般方法和技巧,以及如何將它轉化成圖論問題。 有關的圖論知識,可參閱 J. A. Bondy和 U. S. R. Murty 著 ``Graph Theory with Application'' (MacMillan Press, London and Basingstoke, 1976)。 有關 Ramsey 理論, 可參閱 R. L. Graham, B. L. Rothschild and J. H. Spencer 的專著 ``Ramsey Theory'' (John Wiley and Sons Press,New York,1980)

我們還是從上面提到的幾個例子談起。

例1: 證明,任意一個2色 $4\times 7$ 棋盤 $M$ 一定含有單色矩形, 而且存在不含單色矩形的2色 $4\times 6$ 棋盤。

證明: 設 $M$ 是一個2色 $4\times 7$ 棋盤, $M$ 上共有 $4\times 7=28$ 個方格, 兩種顏色,因此至少有14個方格同色,不妨設 $M$ 上有14個黑色方格。設棋盤 $M$ 的第 $i$ 列上有 $d_i$ 個黑色方格, $i=1,2,\cdots 7$ ,則有 \begin{equation} d_1+d_2+\cdots +d_7=14\hbox{。} \end{equation} 棋盤 $M$ 的第 $i$ 列上由彼此相鄰的方格組成而且上下兩頭的方格都是黑色的長方形的個數為 $C_2^{d_i}$, $i=1,2,\cdots,7$。將棋盤 $M$ 的各列上所有這種長方形都平移到第1列上。 設棋盤 $M$ 不含單色矩形,則平移到第1列上的所有這種長方形不會重疊(注意, 這是關鍵性的一步)。因此平移到第1列上的這種長方形的個數為 $$C_2^{d_1}+C_2^{d_2}+\cdots+C_2^{d_7}\hbox{。}$$ 另一方面,棋盤 $M$ 的第1列上由彼此相鄰的方格組成的長方形 (允許上下兩頭的方格不都是黑色的)的個數為 $C_2^4$。 於是有 $$C_2^{d_1}+C_2^{d_2}+\cdots +C_2^{d_7}\le C_2^4\hbox{,}$$ 即有 $$(d_1^2+d_2^2+\cdots +d_7^2)-(d_1+d_2+\cdots +d_7)\!\le\! 12\hbox{。}$$ 由Cauchy不等式得到, \begin{eqnarray} {1\over 7}(d_1+d_2+\cdots +d_7)^2\nonumber\\ -(d_1+d_2+\cdots +d_7)\le 12\hbox{。} \end{eqnarray} 將式(1)代入式(2)得到, $14\le 12$,矛盾。這就證明, 任意一個2色 $4\times 7$ 棋盤 $M$ 定含有單色矩形。

圖3所示的2色 $4\times 6$ 棋盤不含單色矩形。例1證畢。 評注: 例1的證明方法具有一般意義,仔細分析一下任意一個2色 $4\times 7$ 棋盤 $M$ 一定含有單色矩形的證明,可以發現,其中關鍵的是以下兩步:首先2色 $4\times 7$ 棋盤 $M$ 共有 $4\times 7=28$ 個方格,兩種顏色,其中至少有 ${1\over 2}4\times 7$ 個方格同色。然後抓住其顏色 $c_i$ 不放。這一步用的是抽屜原理。 其次進一步考慮棋盤 $M$ 各列上的 $c_i$ 色方格,其方格數依次為 $d_1,d_2,\cdots d_7$, 則各列上由彼此相鄰方格組成且上下兩頭的方格為 $c_i$ 色的長方形的個數依次為 $C_2^{d_1}$, $C_2^{d_2},\cdots ,C_2^{d_7}$,再將各列上這種長方都平移到第1列。 若棋盤 $M$ 不含單色矩形, 則這些長方形不相重疊,因此其總數不超過第1列上由彼此相鄰方格組成的長方形之個數。 這一步用的是簡單的幾何變換,但有著深刻的圖論意義。務請留意。 至於不含單色矩形的2色 $4\times 6$ 棋盤的存在性,主要採用構造性證明, 其依據仍是抽屜原理。讀者無妨嘗試構造出一個不含單色矩形的2色 $4\times 6$棋盤, 以加深對證明的理解。

例4: 證明, $L(2)=5$。

證明: 由棋盤 Ramsey 數L(2)意義,只要證明, (1)任意一個2色 $5\times 5$ 棋盤 $M$ 一定含有單色矩形,從而 $L(2)\le 5$; (2)存在一個不含單色矩形的2色 $4\times 4$ 棋盤,因此 $L(2)\ge 5$。 於是便有 $L(2)=5$。 (1)設 $M$ 是任意一個2色 $5\times 5$ 棋盤, $M$ 共有 $5\times 5=25$ 個方格,兩種顏色,因此必有13個方格同色,不妨設 $M$ 有13個黑色方格, 而且 $M$ 的第 $i$ 列上有 $d_i$ 個黑色方格, $i=1,\cdots,5$。則有 \begin{equation} d_1+d_2+\cdots+d_5=13 \end{equation} 棋盤 $M$ 的第 $i$ 列上由彼此相鄰方格組成而且上下兩頭的方格都是黑色的長方形共有 $C_2^{d_i}$ 個, $ i=1,2,\cdots,5$ 。將棋盤 $M$ 的各列上這種長方形平移到第1列上。 設棋盤 $M$ 不含單色矩形, 則平移到第1列上的這些長方形不相重疊。 因此棋盤 $M$ 的第1列上這種長方形共有 $C_2^{d_1}+C_2^{d_2}+\cdots+C_2^{d_5}$個。 另一方面, 棋盤 $M$ 的第一列上有5個方格,它們可以組成 $C_{2}^{5}$ 個由彼此相鄰方格組成的長方形。所以有 $$C_2^{d_1}+C_2^{d_2}+\cdots+C_2^{d_5}\le C_2^5\hbox{。}$$ 由上式得到, \begin{eqnarray*} &&(d_1^2+d_2^2+\cdots+d_5^2)\\ &&-(d_1+d_2+\cdots+d_5)\le 20\hbox{。} \end{eqnarray*} 由Cauchy不等式得到, \begin{eqnarray} &&{1\over 5}(d_1+d_2+\cdots +d_5)^2\nonumber\\ &&-(d_1+d_2+\cdots +d_5)\le 20\hbox{。} \end{eqnarray} 將式(3)代入式(4)得到, ${104\over 5}\le 20$,矛盾。 因此棋盤 $M$ 一定有單色矩形,即 $L(2)\le 5$。 (2)圖2所示的2色 $4\times 4$ 棋盤不含單色矩形,因此 $L(2)\ge 5$。 例4證畢。

例5: $L(3)=11$。

證明: 首先證明, $L(3)\le 11$。為此只需證明, 任意一個3色 $11\times 11$ 棋盤 $M$ 一定含有單色矩形, 證明方法與例1和例4相類似。 留作練習。

圖4所示的3色 $10\times 10$ 棋盤 $M$ 不含單色矩形,其驗證方法如下: 棋盤 $M$ 的第1行上有4個帶陰影的方格,它們的右方各行中都只有一個帶陰影的方格。 因此棋盤 $M$ 不含有兩個角在第一行上而且四個角上都是帶陰影的方格的單色矩形; 棋盤 $M$ 的第1行上有3個白色方格,它們位於第3,4和6列上。 考慮棋盤 $M$ 的第 3, 4 和 6 列,除第1行外,其他各行都至多有一個白色方格。 因此棋盤 $M$ 不含有兩個角在第1行上而且四個角都是白色方格的單色矩形; 同樣可以驗證,棋盤 $M$ 不含兩個角在第1行上而且四個角都是帶星的方格的單色矩形。 再考察第2行,如此繼續,即可驗證,棋盤 $M$ 不含單色矩形。於是有 $L(3)\ge 11$ 。 所以 $L(3)=11$ 。例5證畢。 評注: 從例5可知,將例2中的數字12改為11,其結論仍然成立,但若改成10, 則結論不再成立。 確定棋盤Ramsey數 $L(k)$,是一個相當困難的問題,例4和例5給出的 $L(2)=5$ 和 $L(3)=11$ 是所知的幾個棋盤 Ramsey數。下面的定理1給出了棋盤Ramsey數 $L(k)$ 的上界。

定理1: 對於正整數 $k\ge 2$,有 $L(k)\le k^2+k-1\hbox{。}$

證明: 記 $n=k^2+k-1$,由棋盤Ramsey數 $L(k)$ 的意義,只需證明,任意一個 $k$ 色 $n\times n$ 棋盤 $M$ 一定含有單色矩形,為此用反證法。 設 $M$ 是一個不含單色矩形的 $k$ 色 $n\times n$ 棋盤。由於 $M$ 有 $n^2=k^2(k+1)^2-2k(k+1)+1$ 個方格, $k$ 種顏色,因此其中至少有 $k(k+1)^2-2(k+1)+1$ 個方格同色。不妨設 $M$ 有 $r=k(k+1)^2-2(k+1)+1=(n-1)k+n$ 個紅色方格。棋盤 $M$ 的第 $i$ 列上紅色方格數記作 $d_i,i=1,2,\cdots ,n$,則有 \begin{equation} d_1+d_2+\cdots +d_n =r\hbox{。} \end{equation} 考慮棋盤 $M$ 的第 $i$ 列上由彼此相鄰方格組成而且上下兩頭的方格都是紅色的長方形,其個數為 $C_2^{d_i}, i=1,2,\cdots ,n$。將它們都平移到第1列上。 由於棋盤 $M$ 不含單色矩形, 平移到第1列上的這些長方形不相重疊,所以其個數為 $C_2^{d_1}+C_2^{d_2}+\cdots +C_2^{d_n}$。 另一方面, $M$ 的第 1 列上由彼此相鄰方格組成的長方面的個數為 $C_2^n$, 於是有 $$C_2^{d_1}+C_2^{d_2}+\cdots +C_2^{d_n}\le C_2^n\hbox{,}$$ 即有 --\begin{eqnarray*} &&(d_1+d_2+\cdots +d_n)^2\\ &&-(d_1+d_2+\cdots +d_n)\le n(n-1)\hbox{。} \end{eqnarray*} 由 Cauchy 不等式得到 \begin{eqnarray} &&{1\over n}(d_1+d_2+\cdots +d_n)^2\nonumber\\ &&-(d_1+d_2+\cdots +d_n)\le n(n-1)\hbox{。} \end{eqnarray} 將式(5)代入式(6)得到, $${1\over n}r^2-r\le n(n-1)\hbox{,}$$ 即有 $$r^2-nr\le n^2(n-1)\hbox{。}$$ 由於 $r=(n-1)k+n$,所以由上式得到, $$((n-1)k+n)(n-1)k\le n^2(n-1)\hbox{。}$$ 從而有 $$((n-1)k+n)k\le n^2\hbox{。}$$ 將 $n=k^2+k-1$ 代入上式得到, $$n^2-(n-1)k^2-nk=-(k-1)\ge 0\hbox{,}$$ 矛盾。這就證明,任意一個 $k$ 色 $n\times n$ 棋盤 $M$ 一定含有單色矩形。 定理1證畢。 由定理1 可以得到, $L(2)\!\le\! 5,L(3)\!\le\! 11$。 由例4和例5可知, $L(2)\!=\!5,L(3)\!=\!11$。 這說明,定理1所給的關於棋盤Ramsey數 $L(k)$ 的上界是相當好的。 筆者猜想,應有 $L(k)=k^2+k-1$。

先介紹幾個圖論術語,相信它們都是不難理解的,設 $X=\{x_1,x_2,\cdots x_m\}$ 和 $Y=\{y_1,y_2,\cdots y_n\}$ 分別是 $m$ 元集和 $n$ 元集, 記 $V=X\cup Y$,集合 $V$ 中的元素稱為頂點,對於集合 $X$ 中每個頂點 $x$ 和 $Y$ 中每個頂點 $y$,用一條邊將它們連接起來,而集合 $X$ 中每對頂點以及集合 $Y$ 中每對頂點都不連接,得到的圖稱為二部完全圖,記作 $K_{m,n}$。 圖5給出了一個二部完全圖 $K_{4,4},$ 其中小圓圈表示圖 $K_{4,4}$ 的頂點, 連接其中兩個頂點的邊用實線段表示。 注意其中兩條相交的邊的交點不是圖 $K_{4,4}$ 的頂點。

在一個圖 $G$ 中,對於圖 $G$ 的兩個頂點 $x$ 和 $y$,關心的是, 它們之間是否有邊相連,如果 $x$ 和 $y$ 之間有邊相連,則稱 $x$ 和 $y$ 是相鄰的,否則稱為不相鄰。 例如在圖5所示的圖 $K_{4,4}$,頂點 $x_i$ 和 $y_j$ 相鄰, $1\le i,j\le 4$,而任意頂點 $x_i$ 和 $x_j$ 不相鄰, $1\le i\not=j\le 4$, 任意頂點 $y_i$ 和 $y_j$ 不相鄰, $1\le i\not=j\le 4$, 對於圖 $K_{m,n}$, 頂點子集 $X$ 中任意兩頂點不相鄰, 頂點子集 $Y$ 中任意兩頂點不相鄰,而 $X$ 中任意一個頂點和 $Y$ 中任意一個頂點都相鄰。 $(X,Y)$ 稱為 $K_{m,n}$ 的一個二部分劃。

設 $K_{m,n}$ 是一個二部完全圖, $(X,Y)$ 是 $K_{m,n}$ 的二部分劃。 對於頂點子集 $X_1\subseteq X$, $Y_1\subseteq Y$, 令 $X_1$ 中每個頂點和 $Y_1$ 中每個頂點相鄰, 得到的圖稱為 $K_{m,n}$ 的一個二部完全子圖。 例如圖6所示的圖即是圖5中圖 $K_{4,4}$ 的一個二部完全子圖 $K_{2,2}$。

現在考慮圖 $K_{m,n}$ 的染色問題,用 $k$ 種顏色 $c_1,c_2,\cdots ,c_k$ 去染圖 $K_{m,n}$ 的邊, 每一條邊染而且只染一種顏色, 得到的圖稱為 $k$ 色圖, 仍記作 $K_{m,n}$。 當然,對於圖 $K_{m,n}$ 的邊的不同染色方式, 得到的 $k$ 色圖 $K_{m,n}$ 是不同的。圖7和圖8分別給出兩個不同的2色, 圖 $K_{4,4}$,其中實線段表示黑色邊,虛線段表示白色邊。

設 $K_{m,n}$ 是一個 $k$ 色圖,它的頂點集合是 $V=X\cup Y$, 其中 $X\!=\!\{x_1,x_2,\cdots ,x_m\}$, $Y\!=\!\{y_1,y_2,\cdots ,y_n\}$, 而 $K_{r,s}$ 是 $k$ 色圖 $K_{m,n}$ 的一個子圖,其頂點集合為 $V_1=X_1\cup Y_1$, 其中 $X_1=\{x_{i_1},x_{i_2},\cdots ,x_{i_r}\}$,和 $Y_1=\{y_{j_1},y_{j_2},\cdots ,j_{j_s}\}$。如果 $K_{r,s}$ 中每條邊都是 $c_i$ 色的, 則稱 $K_{r,s}$ 是 $c_i$ 色的, 而各邊都是同色的子圖 $K_{r,s}$ 稱為單色的。例如圖7所示的2色圖 $K_{4,4}$ 含有白色子圖 $K_{2,2}$,它的頂點集合是 $\{x_2,x_4\}\cup \{y_1,y_3\}$, 從而2色圖 $K_{4,4}$ 含有單色子圖 $K_{2,2}$, 而圖8所示的2色圖 $K_{4,4}$ 不含單色子圖 $K_{2,2}$ 。

對於圖 $K_{m,n}$ 的邊染色,主要關心的是:

1.對於給定的正整數 $k\ge 2$ , $r$ 和 $s$ ,參數 $m$ 和 $n$ 應滿足怎樣的條件,才能保證任意一個 $k$ 圖 $K_{m,n}$ 一定含有單色子圖 $K_{r,s}$ 。

2.對於給定的正整數 $k\ge 2$ , $r$ 和 $s$ ,求最小正整數 $b_k(K_{r,s})$, 使得當 $n\ge b_k(K_{r,s})$ 時,任意一個 $k$ 色圖 $K_{n,n}$ 一定含有單色子圖。

數 $b_k(K_{r,s})$ 稱為二部Ramsey數。它是Ramsey理論的一個重要研究對象。 所謂棋盤Ramsey數 $L(k)$ 和二部 Ramsey數 $b_k(K_{r,s})$ 有著密切的聯繫。

現在我們來解釋二部完全圖的邊染色問題和棋盤染色問題之間的內在聯繫。 設 $M$ 是一個 $m\times n$ 棋盤,將棋盤 $M$ 上 $m$ 個列從左至右依次編號為 $x_1, x_2,\cdots ,x_m$,其集合記作 $X$。將棋盤 $M$ 上 $n$ 個行從下到上依次編號為 $y_1,y_2,\cdots ,y_n$,其集合記作 $Y$。 記 $V=X\cup Y$。將 $V$ 中的元素視為頂點,令 $Z$ 中每個頂點和 $Y$ 中每個頂點都相鄰,而 $Z$ 中每對頂點都不相鄰, $Y$ 中每對點也都不相鄰, 得到一個圖 $K_{m,n}$。注意, $m\times n$ 棋盤 $M$ 的第 $x_i$ 列和第 $y_j$ 行交叉位置上的方格對應於圖 $K_{m,n}$ 中的邊 $x_iy_j$。 所以給定一個 $m\times n$ 棋盤 $M$,即可按照上述方式確定一個圖 $K_{m,n}$, 使棋盤 $M$ 的每個列 $x_i$ 對應於 $K_{m,n}$ 的頂點 $x_i$,棋盤 $M$ 的每一行 $y_j$ 對應於 $k_{m,n}$ 的頂點 $y_j$, 而 $K_{m,n}$ 連接頂點 $x_i$ 和 $y_i$ 的邊 $x_iy_j$ 對應於棋盤 $M$ 的第 $x_i$ 列和第 $y_j$ 行交叉位置上的方格。這種將棋盤 $M$ 轉化為圖 $K_{m,n}$ 的方法是建立棋盤染色問題和二部完全圖的邊染色問題的關鍵所在。 或者可以簡單地說,圖 $K_{m,n}$ 是 $m\times n$ 棋盤 $M$ 的一種數學模型。 圖5所示的圖 $K_{4,4}$ 即是圖1所示的 $4\times 4$ 棋盤 $M$ 的數學抽象。

現在設 $M$ 是 $k$ 色 $m\times n$ 棋盤,如果棋盤 $M$ 的第 $x_i$ 列和第 $y_i$ 行交叉位置上的方格是 $c_\ell$ 色的,則將圖 $K_{m,n}$ 的邊 $x_iy_i$ 染成 $c_\ell$ 色,於是便得到一個 $k$ 色圖 $K_{m,n}$。 例如圖7和圖8所示的2色二部完全圖即是分別由圖1和圖2所示的2色 $4\times 4$ 棋盤所確定的。這裡應指出的是,對於 $m\times n$ 棋盤 $M$ 的一個由方格組成的矩形, 它的四個角上的四個方格對應於圖 $K_{m,n}$ 中一個子圖 $K_{2,2}$, 它的四條邊相應於矩形的四個角上的四個方格,對於 $k$ 色 $m\times n$ 棋盤 $M$, 它的一個單色矩形對應於 $k$ 色圖 $K_{m,n}$ 中一個單色子圖 $K_{2,2}$, 因此 $k$ 色 $m\times n$ 棋盤 $M$ 含有單色矩形的充要條件是, 它所對應的 $k$ 色圖 $K_{m,n}$ 含有單色子圖 $K_{2,2}$。 於是上面提到的關於棋盤染色的兩個基本問題即是關於二部完全圖的兩個邊染色問題中當 $r=s=2$ 時的特殊情形,而所謂棋盤Ramsey數 $L(k)$ 即是二部Ramsey數 $b_k(K_{2,2})$。 所以由例4和例5有 $b_2(K_{2,2})=5$, $b_3(K_{2,2})=11$。 而定理1即是說, 對於正整數 $k\ge 2$, 有 $b_k(K_{2,2})\le k^2+k-1$。 上面提到的關於棋盤 Ramsey 數 $L(k)$ 的猜想, 用二部 Ramsey 數 $b_k(b_{2,2})$ 的語言來說,即是 $b_k(K_{2,2})=k^2+k-1$ 確定二部Ramsey數 $b_k(K_{r,s})$ 的值是相當困難的,

除上面提到的二部Ramsey 數 $b_2(K_{2,2})=5$ 和 $b_3(K_{2,2})=11$ 之外,至今所知的是, 1975年Beineke和Schwenk(On a partition form of the Ramsey problem, in Proceedings of the Fifth British Combinatorial Conference 1975 (eds. C. St. J. A. Nash-Williams and J. Sheehan), Congressus Numerantium X V, Utilitas Mathematica, Winnipeg,1975, pp.17-22)求得 $b_2(K_{3,3})=17$, 1974年Irving (A bipartite Ramsey problem and the Zarankiewicz numbers, Discrete Math. 9(1974), 251-264)求得的 $b_2(K_{3,4})=25$ 和 $b_2(K_{r,s})=33$, 這就迫使人們去尋求二部Ramsey數 $b_k(K_{r,s})$ 的上界。

定理2: 設 $k$和 $n$ 是正整數, $\pi\!=$ $(d_1,d_2,\cdots ,d_n)$ 是非負整數序列, 記 $\sigma(\pi)=d_1+d_2+\cdots+d_n$。 所有滿足 $\sigma (\pi)\ge {n^2\over k}$ 的非負數整數序列 $\pi$ 的集合記作 $S$, 即 $$S=\{\pi=(d_1,d_2,\cdots ,d_n)|\sigma(\pi)\ge{n^2\over k}\}\hbox{。}$$ 對於 $\pi=(d_1,d_2,\cdots ,d_n)\in S$ ,記 $C(\pi)=C_r^{d_1} +C_r^{d_2}+\cdots +C_r^{d_n}$ ,當非負整數序列 $\pi(d_1,d_2,\cdots ,d_n)$ 遍歷集合 $S$ 時, $C(\pi)$ 的最小值記作 $g_k(n)$,即 $$g_k(n)=\min_{\pi\in S}\{C(\pi)\}\hbox{。}$$ 則有 \begin{equation} b_k(K_{r,s})\le\min\{n|g_k(n)\gt (s-1)C_r^n\}\hbox{。} \end{equation}

證明: 設 $n$ 是所有滿足 $g_k(n)\gt (s-1)C_r^n$ 的正整數 $n$ 之最小值, 先弄清正整數 $n$ 的涵義,記 $$T=\{n|g_k(n)\gt (s-1)C_r^n\}\hbox{。}$$ $T$ 是非負整數集合, $n$ 是 $T$ 中之最小正整數,因此有 $g_k(n)\gt (s-1)C_r^n$。 由於 $g_k(n)$ 是正整數集合 $\{C(\pi)|\pi\in S\}$ 的最小值,因此對於每個滿足 \begin{equation} \sigma(\pi)=d_1+d_2+\cdots +d_n\ge{n^2\over k} \end{equation} 的非負整數序列 $\pi=(d_1,d_2,\cdots ,d_n)$,均有 \begin{eqnarray} C(\pi)&=&C_r^{d_1}+C_r^{d_2}+\cdots +C_r^{d_n}\nonumber\\ &\ge&g_k(n)\gt (s-1)C_r^n\hbox{。} \end{eqnarray} 現在為證明結論(1),只需證明,任意一個 $k$ 色圖 $K_{n,n}$ 一定含有單色子圖 $K_{r,s}$。 用反證法,設 $k$ 色圖 $k_{n,n}$ 不含單色子圖 $K_{r,s}$, 並且設 $K_{n,n}$ 的頂點集合是 $V=X\cup Y$,其中 $X=\{x_1,x_2,\cdots ,x_n\}$, $Y=\{y_1,y_2,\cdots ,y_n\}$。由於 $K_{n,n}$ 有 $n^2$ 條邊, $k$ 種顏色,所以 $K_{n,n}$ 至少有 $[{n^2\over k}]+1$ 條邊同色, 不妨設 $K_{n,n}$ 有 $[{n^2\over k}]+1$ 條 $c$ 色邊。 設集合 $X$ 中頂點 $x_i$ 連有 $d_i$ 條 $c$ 色邊, $i=1,2,\cdots ,n$,則 $$d_1+d_2+\cdots +d_n\ge{n^2\over k}\hbox{。}$$ 記 $\pi=(d_1,d_2,\cdots ,d_n)$,則 $\pi$ 是非負整數序列, 而且 $\sigma(\pi)\ge{n^2\over k}$,從而 $\pi\in S$。對於集合 $X$ 中每個頂點 $x_i$, 考慮集合 $Y$ 中這樣的 $r$ 元子集 $Z$, 頂點 $x_i$ 和 $Z$ 中每個頂點 $z$ 連的邊 $x_i$ 都是 $c$ 色的。 由於頂點 $x_i$ 連有 $d_i$ 條 $c$ 色邊,其中每 $r$ 條邊便確定 $Y$ 中一個這樣的 $r$ 元子集 $Z$。所以這樣的 $r$ 元子集有 $C_2^{d_i}$ 個, 從而 $Y$ 中這樣的 $r$ 元子集 $Z$ 的個數為 $$C(\pi)=C_r^{d_1}+C_r^{d_2}+\cdots +C_r^{d_n}\hbox{。}$$ 注意,這是從集合 $X$ 的頂點來考慮 $Y$ 中這樣的 $r$ 元子集 $Z$ 的計數。 我們也可以從另一方面來考慮 $Y$ 中這樣的 $r$ 元子集的計數: 對於 $Y$ 中一個 $r$ 元子集 $Z$,考慮 $X$ 中這樣的頂點 $x$, 它和 $Z$ 中每個頂點 $z$ 連的都是 $c$ 色邊 $xz$。這樣的頂點 $x$ 的個數記作 $\beta(Z)$。當 $Z$ 遍歷 $Y$ 中所有的 $r$ 元子集時, 則所有 $\beta(Z)$ 之和即是 $Y$ 中所有這樣的 $r$ 元子集 $Z$ 的個數, 於是得到 $$\sum_{Z\subseteq Y}\beta(Z)=C_r^{d_1}+C_r^{d_2}+\cdots +C_r^{d_n}=C(\pi)$$ 由於 $K_{n,n}$ 不含單色子圖 $K_{r,s}$,所以對於 $Y$ 中每個 $r$ 元子集 $Z$, 均有 $\beta(Z)\le s-1$,而 $Y$ 中 $r$ 元子集的個數是 $C_r^n$,因此 $$(s-1)C_r^n\ge\sum_{Z\subseteq Y}\beta(Z)=C(\pi)\hbox{。}$$ 由於 $\pi\in S$,所以由式(3)得到, $$(s-1)C_r^n\ge C(\pi)\ge g_k(n)\gt (s-1)C_r^n\hbox{,}$$ 矛盾,定理2證畢。

定理2是關於二部Ramsey數$b_k(K_{r,s})$ 的一個基本定理, 它是1956年 Erdös 和Rado (A partition calculus in set theory, Bull. Amer. Math. Soc., 62(1956), 427-489)首先發現並證明的。這裡採用的是1969年Chvátal (On finite polarized partition relations Canad. Math. Bull. 12 (1969), 321-326) 給出的精彩證明,讀者只要仔細比較定理1和定理2的證明即可發現, 除表述形式不同外, 其方法是相同的。 下面是定理2的幾個推論。

推論1: $b_2(K_{2,s})\le 4s-3$

證明: 採用定理2的記號,並令 $r=2$,記 $$T\{n|g_k(n)\gt (s-1)C_2^n\}$$ 根據定理2,只需證明, $n=4s-3\in T$。 對於給定的 $s$ 和 $n=4s-3$,集合 $$S=\{\pi=(d_1,d_2,\cdots ,d_n)|\sigma(\pi)\ge{n^2\over 2}\}$$ 是非空的,因此集合 $\{C(\pi)|\pi\in S\}$ 是一個非空的正整數集合, 所以其最小值 $g_2(n)$ 總是存在的。設 $\pi=(d_1,d_2,\cdots ,d_n)\in S$, 即設 \begin{equation} \sigma(\pi)=d_1+d_2+\cdots +d_n\ge{n^2\over 2}, \end{equation} 而且 $$C(\pi)=C_2^{d_1}+C_2^{d_2}+\cdots +C_2^{d_n}=g_2(n)\hbox{。}$$ 如果 $n=4s-3\not \in T$,則 \begin{eqnarray*} C(\pi)&=&C_2^{d_1}+C_2^{d_2}+\cdots +C_2^{d_n}=g_2(n)\\ &\le&(s-1)C_2^n\hbox{。} \end{eqnarray*} 於是 \begin{eqnarray*} &&(d_2^2\!+\!d_2^2\!+ \!\cdots \!+\!d_n^2)\!-\!(d_1\!+\!d_2\!+\!\cdots \!+\!d_n)\\ &\le& (s-1)n(n-1)\hbox{。} \end{eqnarray*} 由Cauchy不等式得到, $${1\over n}\sigma(\pi)^2-\sigma(\pi)\le(s-1)n(n-1)\hbox{。}$$ 將式(3)代入上式得到, $$(n-1)^2\lt (n-1)^2+1\!\le\! 4(s-1)(n-1)\hbox{。}$$ 所以 $n-1\lt 4(s-1)$,即 $n\lt 4s-3$,矛盾,推論2證畢。

推論2: 當 $k\ge 2$ 時, $b_k(K_{2,2})=L(k)$ $\le k^2+k-1$。

證明: 和推論1的證明完全相同,留作練習。 從上面的討論可以看到,棋盤染色問題和二部完全圖的邊染色問題有著密切的內 聯繫。而後者又和Ramsey理論中的二部Ramsey數 $b_k(K_{r,s})$ 緊密相關。 這就是為什麼數學競賽中經常會出現棋盤染色的試題的原因所在。 對於指導學生參加數學競賽的老師,通過數學競賽試題的分析和講解, 不但講清楚解題的方法和技巧,而且也講清楚試題的數學背景, 從而將參賽學生引導到現代數學上來,這無疑是十分必要的。

---本文作者任教於中國科學技術大學數學系---