數學傳播

1. 前言

匈牙利數學家 László Lovász ^{1 1} László Lovász 生於 1948 年 3 月 9 日, 他的工作主要在組合學, 於 1999 年獲得 Wolf 獎, 以及 Knuth 獎, 於 2010年 獲得 Kyoto 獎。他曾獲得三次 (1964, 1965, 1966) 國際數學奧林匹亞金牌, 1970 年獲得匈牙利科學院的博士學位。 Lovász 主要在 Eötvös 大學工作, 於 1975$\sim$1982 曾主持 Szeged 大學幾何學系, 1990 年代在 Yale 大學, 並在微軟研究中心直到 2006 年再回 Eötvös 大學。他從2007年1月1日到2010年12月31日這四年擔任國際數學聯盟主席。 於 1999 年獲得 Wolf 獎 ^{2 2} 1976 年 Ricardo Subiranay Lobo Wolf 和他太太 Francisca 捐出一千萬美金, 創立 Wolf 基金會, 獎勵在農業、化學、數學、醫學、物理、藝術六大領域有傑出貢獻的科學家。 他的得獎理由是 「在離散數學裡獲得突破性的基本結果, 其在純數學、應用數學以及理論計算機科學都有十分重要的應用。 藉由引進一些仰賴於幾何、多面體及拓樸技術的深刻數學方法, 他解決了許多重要的問題, 包括完美圖猜測, Kneser猜測及決定五邊形 Shannon 容量$\cdots$」。

這篇文章主要的目的就是要來介紹 Lovász 決定五邊形 Shannon 容量的精彩推導, 順帶談論 1960 年代離散數學家所關心的一些議題, 我們先從圖論談起。

2. 圖論緣起

很少有一個數學次領域可以說是從那一年誕生的, 而今, 大部分的人都肯定, 圖論的產生源自於1736年歐拉(Euler)的一篇討論七橋問題的文章 [1]。

在十八世紀的時候, 東普魯士的 Königsburg (現今俄羅斯的 Kaliningrad) 市有一條 Pregel 河 (現今 Pregolya 河) 流經, 河的中心有兩座小島, 小島與河的兩岸有七座橋相連接 (參見圖 1 左邊之示意圖)。 當地流傳一則這樣的謎題, 要如何才能從某一塊土地開始, 將每一座橋恰好經過一次。

一般觀察力略為敏銳的人在經過一些嘗試之後, 很快就會發現這是不可能的。 當做數學家, 歐拉給出一個「精確」的說法。 首先, 他進一步將土地和橋的示意圖抽象, 用四點代表四塊土地, 一些點對之間的曲線 (邊) 代表橋, 如圖1右邊所示。 七橋問題於是變成, 是否可以從某一點開始, 沿著邊走到另一點, 再沿著另一條邊走到另一點, 依此類推, 目的是要將每一條邊都恰好走過一次。

歐拉的思考不只在七橋的特殊情況, 他考慮一般的圖。 對於圖中的每一點 $v$, 定義其度數 $d(v)$ 為與 $v$ 相鄰的邊數, 如圖 1 中的 $d(A) = d(C) = d(D) = 3$ 且 $d(B) = 5$, 當我們將圖中的所有點的度加起來時, 每加一個點的度, 我們順便將與他相鄰的邊做一個記號, 所以度的總和就是記號的數目; 但是因為每一條邊恰有兩個端點, 所以會得到兩個記號, 因此歐拉得到下面的公式： $$\sum_v d(v)=2m$$ 其中 $m$ 是邊的數目。以上的這個證明方法就是所謂的雙重計數法 (double counting), 是十分有用的基礎手段。 由度數和的公式, 我們知道, 度數為奇數的點有偶數個, 如圖 1 的圖就有四個奇度點。

歐拉說明七橋問題沒有解的方法如下。 假如存在一個從 $x$ 到 $y$ 的走法 (如今在圖論上稱為道路), 如果 $z$ 有異於 $x$ 和 $y$, 則當我們借由某一條邊走進 $z$ 之後, 必借由另一邊走出 $z$ 到另外一點, 因此, 和 $z$ 相鄰的邊必然成對出現, 得知 $d(z)$ 是偶數。但是圖1的四個點, 都是奇點, 所以是不可能的。

歐拉的論文比較大的篇幅是在討論反方向。它說明了, 只要圖是連通而且各個點的度都是偶數, 那麼一定可以從任意點出發, 沿著點邊的走法, 走出一條道路, 並且每一條邊只用到恰好一次, 最後回到原來出發的點。 ^{3 3} 詳細閱讀歐拉的論文, 可以發現, 其實他的論證略有不完備, 但要將它改正卻也不困難。因此, 現在人們還是將此定理歸功於他, 並且將這樣的路徑以他命名, 稱為歐拉路徑。

如果連通圖有 $2k$ 個奇點, 則將其兩兩配對, 以這些點為端點加上 $k$ 條新的邊, 成為一個只有偶點的連通圖, 因此, 存在一條將每邊恰走過一次又回到原出發點的道路; 再將新加入的 $k$ 條邊拆除, 會變成 $k$ 條道路。 所以七橋問題中其實是要走兩段道路, 而不能由某地出發將每座橋恰走過一次, 到達另一處。

3. König 的第一本書

從 1736 年到 1936 年這兩百年間, 可以說是圖論的春秋戰國時代, 不同領域的研究人員在他們各自的岡位上, 以不同的名稱, 不同的內容, 探索與歐拉發現的圖一樣的概念 (參見 [2])。 一直到 1936 年, König 撰寫了圖論的第一本書[3], 圖論在數學上於是有了正式的定位。 從 1936 到現在不到一百年, 圖論的發展迅速, 各種理論及應用, 在數學及其他學科中都得到極多的肯定, 相關的書籍成幾何級數增加。

為了解釋方便, 我們來定下一些的基本用語。 所謂圖是指一有序對 $G = (V, E)$, 其中 $V$ 是非空的有限集, 其元素稱為 (頂) 點, $E$ 是一些 $V$ 的相異二元無序對的集合, 即 $E\subseteq \{ e: e\subseteq V,|e|=2\}$ 其元素稱為邊。 有的時候, 我們用 $V(G)$ 表示圖 $G$ 的點集, 而 $E(G)$ 表示圖 $G$ 的邊集。 方便起見, 我們常將一條邊 $e = \{u, v\}$ 直接寫成 $uv$, 因此 $uv$ 和 $vu$ 是相同的。 此時, 我們說 $u$ 和 $v$ 是 $e$ 的端點, 也說 $e$ 和 $u$ (及 $v$) 相連, 並說 $u$ 和 $v$ 相鄰, 或者說 $u$ 是 $v$ 的鄰居, 而用 $N(v)$ 表示 $v$ 的所有鄰居所構成的集合。

為了視覺上的方便, 我們常常將一個圖具體地劃出來, 如圖 2 表示 $V = \{a, b, c, d, e\}$ 及 $E = \{ab, ae, bc, be, cd, de\}$ 的圖。 如果圖中點的名稱暫時不重要時, 我們也可能不將它們標出來, 一直等到有需要的時候再來標示, 如果只有少數點的名字必須用到, 我們也可能只標示出那些點的名字。

圖的定義也可以有種種變化。如果我們允許兩點之間可以不只連一條邊, 就可以產生有重邊的重圖; 如果我們允許一條邊的兩端點相同, 就產生有迴邊的近圖; 如果我們允許圖的邊有方向 (此時 $(u,v) = uv$ 和 $(v,u) = vu$ 視為不同), 就產生有向圖; 如果我們允許 $V(G)$ 為無窮集合, 就產生無窮圖。

一個圖中的一條道路是指一條點邊相間的序列 $v_0 e_1 v_1 e_2 \cdots e_k v_k$ 其中的 $v_{i-1}$ 和 $v_i$ 是 $e_i$ 的端點; $v_0$ 稱為此道路的起點、 $v_k$ 為終點、 $k$ 為長; 滿足 $v_0 = v_k$ 的道路稱為封閉道路, 滿足 $v_0 \not= v_k$ 的道路稱為開放道路。 如果一個圖沒有重邊或迴圈, $e_i$ 就被 $v_{i-1}$ 和 $v_i$ 完全決定, 因此我們可以用 $v_0 v_1 \cdots v_k$ 表示道路。 一條行跡是指邊不重複的道路, 而一條路徑是指點不重複的道路, 一條歐拉迴路是指一條將每一條邊恰用一次的封閉行跡。 一個圖是連通的, 如果任何兩點之間均有一條道路。 歸結來說, 歐拉的定理如下所述。

定理 (歐拉). 如果 $G$ 沒有度為 0 的點, 則 $G$ 存在歐拉迴路若且唯若 $G$ 是連通的而且其中每一點均有偶度數。

一個圖稱為二部圖 (bipartite graph), 如果其頂點集可以分割成 $A$ 和 $B$, 使得圖中每一條邊恰有一端點在 $A$、 另一端點在 $B$。 圖的一個配對是指一邊集, 其中每兩條邊都沒有共同端點。 二部圖配對的研究是二十世紀初流行的議題, König 當年就是著迷於此, 對圖論大感興趣, 才會寫下圖論的第一本書, 其中二部圖配對佔了不少篇幅。而著名的匈牙利算法就是 König 和 Egerváry 用演算法的觀點求二部圖中最大配對的方法, 參見 [4, 5]。

4. 圖的點著色

圖的著色源自於十九世紀中葉英國的一位學生 Francis Guthrie (後來成為南非大學數學教授) 提出的平面圖四著色問題, 這個問題歷經一百多年的研究, 產生了不少研究方向和工具, 最後在 1977 年時由Appel、 Haken 和 Koch [6, 7] 藉由電腦的幫助, 透過「放電論證法」證明了四色定理。 他們的方法依賴電腦的大量計算, 很難讓數學家們都滿意, 因此至今仍有人還在繼續努力, 希望能找到一個簡潔而「可閱讀」的證明。 正如同當時人們的評語所說的：「一個好的數學證明應該像一首詩, 而這根本是電話簿。」 雖然他們的證明後來被 Robertsen、 Sanders、 Seymour 和 Thomas 四人 [8] 簡化, 不過還是不能避免利用到電腦來驗證。

我們著眼於圖的著色, 不在四色定理而在其有許多的實際應用, 諸如排時、排序、時間表、頻道分配、資源分配、實驗設計等等議題, 都可以借由圖的著色來解決。

一個圖 $G$ 的正常 $k$-著色是指一函數 $f:V(G)\to \{1,2,\ldots,k\}$ 使得兩點 $x$ 和 $y$ 相鄰時恆有 $f(x)\not=f(y)$。 圖 $G$ 的著色數 $\chi(G)$ 是存在正常 $k$-著色的最小 $k$ 值。 圖 2 中的五個點的圖 $G$ 可以用 $f(a) = f(c) = 1$、 $f(b) = f(d) = 2$、 $f(e) = 3$ 著色, 所以 $\chi(G)\le 3$; 事實上 $\chi(G) = 3$, 因為 $a$、 $b$、 $e$ 三個點要著不同顏色。

圖 $G$ 的一個獨立集 (點團) 是指一集合 $S\subseteq V(G)$, 其中的任意相異兩點均不相鄰 (相鄰), 而圖 $G$ 的獨立數 $\alpha (G)$ (點團數 $\omega (G)$) 是指獨立集 (點團集) 的最多點數。 由正常 $k$-著色 $f$ 的定義可以知道, $f^{-1}(i)=\{x\in V(G):f(x)=i\}$ 是一個獨立集, $i=1,2,\ldots,k$。 所以著色數 $\chi(G)$ 其實也是可以將 $V(G)$ 分割成最少的獨立集的個數, 其中每一個獨立集 $f^{-1}(i)$ 稱為一個色類。

著色之所以可以有廣泛的運用, 是因為很多應用實際上是要將一些物件分割成具有某性質的子類, 如果我們將這些物件視為一個圖的點集, 將不具特定性質的兩物件連邊, 常常可以將問題化為圖著色。 今舉一例說明如下。

某大學有 $n$ 門課同時要開設, 第 $i$ 門課的開設時段為 $[a_i,b_i]$ 區間, 教務處的任務是要將這些課程排出來, 利用越少的教室越好, 當然, 時段重疊的兩門課要排在不同的教室。我們可以造一個圖 $G$, 其頂點集 $V(G)=\{v_1,v_2,\ldots,v_n\}$ 表示這 $n$ 門課, 其邊集表達課的衝突性, 即 $E(G)=\{v_iv_j:i\not=j$ 且 $[a_i,b_i]\cap[a_j,b_j]\not=\emptyset\}$。 如果將可以排用同一教室的兩門課著同色, 就是一個正常著色, 所以 $\chi(G)$ 其實就是要求的教室的最少間數。

上述利用實數軸上的區間定義出來的圖稱為區間圖, 求區間圖的著色數在1960年代是很熱門的話題。

5. 完美圖起源

我們先來看看如何求區間圖的著色數, 如果區間圖 $G$ 的頂點 $v_i$ 對應的區間為 $[a_i,b_i]$, 為了方便起見, 假設 $a_1\le a_2\le\cdots \le a_n$。

我們利用貪求法將 $G$ 著色： $i$ 從 1 到 $n$ 逐一將 $v_i$ 著為「沒有被 $j\lt i$ 而 $[a_i,b_i]\cap[a_j,b_j]\not=\emptyset$ 的 $v_j$ 用到的最小正整數。」

由上述的著色方法可以看出這是一個正常著色。假設總共用到 $k$ 色, 我們將用對偶方法證明, 其實 $\chi(G)=k$。 首先, 對於任意圖 $G$ 我們恆有弱對偶不等式： $$\omega(G)\le\chi(G),$$ 這是因為 $G$ 中的任意點團中的相異點都要用不同的顏色去著。 回到區間圖的著色, 如果 $v_i$ 用了第 $k$ 色, 之所以如此, 是因為存在 $j_1,j_2,\ldots,j_{k-1}$ 小於 $i$, 使得 $v_{jr}$ 用了第 $r$ 色 $(1\le r\le k-1)$, 而且 $[a_{jr},b_{jr}]$ 和 $[a_i,b_i]$ 相交, 但是 $j_r\lt i$ 表示 $a_{jr}\le a_i$, 因而 $[a_{jr},b_{jr}]$ 包含點 $a_i$, 這表示 $\{v_{j_1},v_{j_2},\ldots,v_{j_{k-1}},v_i\}$ 是一個 $k$ 點的點團, 因此 $$k\le \omega(G)\le\chi(G)\le k,$$ 所以證明了 $\omega(G)=\chi(G)=k$。

會有上述的好結果, 本質上是 $G$ 具有 $\omega(G)=\chi(G)$ 這樣「完美」的性質, 這在下述 Shannon 的工作中會再度出現。雖然如此, Berge 在 1960 年代在定義 $G$ 的完美性時卻有更強的要求。 一個圖 $G$ 稱為完美圖 (perfect graph), 如果對其任意導出子圖 $H$ 均有 $\omega(H)=\chi(H)$。 $H$ 是 $G$ 的導出子圖指的是 $V(H)\subseteq V(G)$ 且 $E(H)=\{xy\in E(G):x,y\in V(H)\}$。 Berge 這樣定義是因為縱使 $\omega(G)=\chi(G)$, 它可能也是一個內部包含架構很差的圖。舉例來說, 不管 $H$ 是什麼圖, 如果他有 $n$ 點, 則考慮 $G=H\cup K_n$ 時, 都會有 $\omega(G)=\chi(G)=n$。

早年在考慮完美圖時, 除了 $\omega$ 和 $\chi$ 這對參數之外, 人們也考慮 $\alpha$ 和 $\theta$, 其中 $\theta(G)$ 是指將 $G$ 的點集分割成最少的點團的個數。 因為 $G$ 中的獨立集 (點團) 在 $G$ 的補圖 $G^c$ 中是點團 (獨立集), 所以 \begin{eqnarray*} \alpha(G)=\omega(G^c)&\hbox{且}&\theta(G)=\chi(G^c)\\ {\hbox{或者是}} \omega(G)=\alpha(G^c)&\hbox{且}&\chi(G)=\theta(G^c)\hbox{。} \end{eqnarray*} 所以, 研究 $\omega$ 和 $\chi$ 其實等同在補圖研究 $\alpha$ 和 $\theta$。以下 Shannon 的工作是用 $\alpha$ 和 $\theta$ 描述的。

Shannon [9] 在 1956 年研究零錯信息傳輸, 他希望傳輸的信息都要不混淆。 假設我們有一符號集 $V$, 我們可以造一圖 $G$, 以 $V$ 為點集, 而其邊集 $E = \{xy:$ $x$ 和 $y$ 造成混淆$\}$。 兩條長度為 $m$ 的信息 $x_1x_2\cdots x_m$ 和 $y_1y_2\ldots y_m$ 不混淆是指對某一個 $i$ 有 $x_i=y_i$ 且 $x_i$ 和 $y_i$ 不混淆。 目標是固定 $m$ 之後, 想要找一包含兩兩不混淆的長度為 $m$ 的信息集合。一個簡單的方法是找一大小為 $\alpha(G)$ 的獨立集 $S$, 則 $$\{x_1x_2\cdots x_m:x_i\in S\}$$ 是一個大小為 $\alpha(G)^m$ 的信息集。問題是, 能不能做得更好？

答案是, 有時確實可以做得更好, 以 $G=C_5$ 為例子, 此時 $V(C_5)=\{a,b,c,d,e\}$ 且 $E(C_5)=\{ab,bc,cd,de,ea\}$, 是為五邊形圖。 易知 $\alpha(C_5)=2$, 因此上述的造法得到大小為 $2^m$ 的不混淆信息集。 但是我們可以考慮這樣的集合, 對於每一個奇數 $i$, $x_ix_{i+1}$ 是取自 $\{aa,bc,ce,db,ed\}$ 有五種取法, 這樣會造成一大小為 $5^{\lfloor m/2\rfloor}$ 的不混淆信息集, 這遠比 $2^m$ 大很多。

為了簡化敘述, 我們來定義圖的強乘積 (strong product)。 如果 $G$ 和 $H$ 是兩圖, 其強乘積 $G\otimes H$ 的頂點集 $V(G\otimes H)=V(G)\times V(H)$, 而邊集 $E(G\otimes H)=\{(x,y)(x',y'):(x=x'$ 或 $xx'\in E(G))$ 且 $(y=y'$ 或 $yy'\in E(H))\}$。

當 $m$ 是正整數時, $G^m=G\otimes G\otimes \cdots \otimes G$ (共 $m$ 次)。因此, Shannon 所要求的數其實就是 $\alpha(G^m)$。 因為對任意 $G$ 和 $H$ 恆有 $$\alpha(G\otimes H)\ge \alpha(G)\cdot \alpha(H),$$ 我們得知 $\alpha(G^m)\ge \alpha(G)^m$。 前述 $G=C_5$ 的例子中 $\alpha(C_5^m)\ge\alpha(C_5)^m=2^m$, 當然後來我們更進一步知道 $\alpha(C_5^m)\ge 5^{\lfloor m/2\rfloor}$。 一般而言, $\alpha(G^m)$ 都是指數成長, 為了方便, 我們考慮 $\alpha(G^m)^{1/m}$, 而當 $m\to\infty$, 其極限總是存在 ^{4 4} 一般來說, 如果函數 $f:{\mathbb N}\to {\mathbb R}^+$ 滿足 $f (m+n)\ge f(m)f(n)$ 對任意 $m,n\in {\mathbb N}$ 恆成立, 則 $\lim_{m\to\infty} f(n)^{1/n}$ 存在。這是著名的Fekete引理。 於是就可以定義 $\psi(G)=\lim_{m\to\infty}\alpha(G^m)^{1/m}$, 我們稱它為 Shannon 容量 (Shannon capacity)。 回到上述的 $C_5$, 到底 $\psi(C_5)$ 是多少？ 我們已經知道 $\psi(C_5)\ge \sqrt{5}$ 了。

在討論 Lovász 證明 $\psi(C_5)=\sqrt 5$ 之前, 讓我們回到完美圖。 首先, $\omega$ 和 $\chi$ 之間的弱完美不等式 $\chi(G)\ge \omega(G)$ 一樣, 我們也有 $\theta(G)\ge\alpha(G)$, 因此, 再加上一些推導就有 $$\alpha(G)\alpha(H)\le \alpha(G\otimes H)\le \theta(G\otimes H)\le \theta(G)\theta(H),$$ 更一般而言, $\alpha(G)^m\le\alpha(G^m)\le\theta(G^m)\le\theta(G)^m$ 或者 $\alpha(G)\le\alpha(G^m)^{1/m} \le\theta(G^m)^{1/m}\le\theta(G)$。 如果 $\alpha(G)=\theta(G)$, 我們就可以得到 $\psi(G)=\alpha(G)$ 這樣好的公式。 這其實也是當年 Berge 他們急於問, 何時 $\alpha(G)=\theta(G)$ 的原因。但如同前面所提, 一般是要 $\alpha(H)=\theta(H)$ 對 $G$ 所有導出圖 $H$ 都成立比較容易說。

因為 $G$ 的 $\omega$ 和 $\chi$ 關係等同於其補圖 $G^c$ 的 $\alpha$ 和 $\theta$ 的關係, 我們事實上, 是在研究 $G$ 的完美性和 $G^c$ 的完美性。第一個非完美的最小圖是 $C_5$, 這也是為何 $\psi(C_5)\ge \sqrt{5} \gt 2=\alpha(C_5)$ 的原因。在研究完美圖的過程, Berge 發現 $G$ 和 $G^c$ 中只要有一個是完美圖, 另一個也是, 例如區間圖就如此; 完美圖不能有 $C_{2k+1}$ 和 $C^c_{2k+1}$ ($k\ge 2$) 為其導出子圖, 而似乎反過來也成立。因此他寫下了兩個著名的猜測：

• (C1) 圖 $G$ 為完美圖若且唯若 其補圖 $G^c$ 為完美圖。
• (C2) 圖 $G$ 為完美圖若且唯若 $G$ 不含 $C_{2k+1}$ 及 $C^c_{2k+1}$ ($k\ge 2$) 為導出子圖。

其中 (C2) 如果對的話, 可以推得 (C1) 也對, 所以 (C1) 也被稱為完美圖弱猜測, 而 (C2) 就被稱為完美圖強猜測。完美圖弱猜測在 1972 年被 Lovász [7, 8] 證明出來, 這也是 Lovász 獲得 Wolf 獎的得獎理由之一, 然而完美圖強猜測則一直要等到 2006 年才被 Chundnovsky、 Robertson、 Seymous、 Thomas 四人 [9] 證明出來。

6. Lovász 的巧思

現在讓我們來談談 Lovász 如何算 $\psi(C_5)$ 的方法。 對於 ${\Bbb R}^{n}$ 中的向量 $x=(x_1,x_2,\ldots$, $x_n)$ 及 ${\Bbb R}^m$ 中的向量 $v=(v_1,v_2,\ldots,v_m)$, 我們用 $x\circ v$ 來表示他們的張量積 (tensor product), 它是一個 ${\Bbb R}^{mn}$ 中的向量 $(x_1v_1,x_2v_1,\ldots,x_nv_1,x_1v_2,x_2v_2,\ldots,x_nv_2,\ldots$, $x_1v_m, x_2v_m$, $\ldots,x_nv_m)$。 我們用 $\langle x,y\rangle $ 表示 ${\Bbb R}^m$ 中的兩個向量 $x$ 和 $y$ 的內積 (inner product), 也就是 $\sum_{i=1}^n x_iy_i$。 此時對於 ${\Bbb R}^n$ 中的向量 $x$ 和 $y$, 以及 ${\Bbb R}^m$ 中的向量 $v$ 和 $w$, 我們恆有 $$(x\circ v,y\circ w)=\langle x,y\rangle\cdot \langle v,w\rangle(*)$$ 假如圖 $G$ 的頂點集 $V(G)=\{1,2,\ldots,n\}$。我們稱 $G$ 的一個標準正交代表(orthonormal representation) 是一組歐式空間的單位向量 $(v^1,v^2,\ldots,v^n)$, 使得對於不相鄰的 $i$ 和 $j$ 必有 $v^i$ 和 $v^j$ 垂直。 顯然, 取一組兩兩互相垂直的單位向量是任意 $n$ 點圖的標準正交基底, 所以這樣的代表總是存在的。 由式子 $(*)$ 顯然有：

引理1. 如果 $(u^1,u^2,\ldots,u^n)$ 和 $(v^1,v^2,\ldots,v^n)$ 分別是 $G$ 和 $H$ 的標準正交代表, 則所有 $u^i\circ v^j$ 將形成 $G\otimes H$ 的一個標準正交代表。

定義一個標準正交代表 $(u^1,u^2,\ldots,u^n)$ 的值 (value) 為 $$\min_c\max_{1\le i\le n}\frac 1{\langle c,u^i\rangle^2}$$ 其中 $c$ 遍歷所有單位向量, 而當中達到最小值的那個 $c$ 稱為此代表的柄 (handle)。 我們用 $\phi(G)$ 表示 $G$ 的所有標準正交代表的值當中最小的值, 並稱那個達到最小值的代表為最佳代表 (optimal representation)。

引理2. $\phi(G\otimes H)\le \phi(G)\phi(H)$。

證明: 設 $(u^1,u^2,\ldots,u^n)$ 和 $(v^1,v^2,\ldots,v^n)$ 分別為 $G$ 和 $H$ 的最佳代表, 其柄分別為 $c$ 和 $d$。 由式 $(*)$ 知, $c\circ d$ 為單位向量, 再套用式子 $(*)$, 可知 $$\phi(G\otimes H)\le \max_{i,j}\frac 1{\langle c\circ d, u^i\circ v^j\rangle^2} =\max_{i,j}\frac 1{\langle c,u^i\rangle^2\langle d,v_j\rangle^2}=\phi(G)\phi(H)\hbox{。}{\Box}$$

引理3. $\psi(G)\le \phi(G)$。

證明: 我們首先證明 $\alpha(G)\le \phi(G)$。 令 $(u^1,u^2,\ldots,u^n)$ 是 $G$ 的一個帶柄 $c$ 的最佳標準正交代表。 不失一般性假設 $\{1,2,\ldots,k\}$ 是 $G$ 中的一個最大獨立集, $u^1,u^2,\ldots,u^n$ 兩兩垂直, 所以 $$1=\|c\|^2\ge\sum_{i=1}^k \langle c,u^i\rangle^2\ge \frac{\alpha(G)}{\phi(G)},$$ 由此以及引理 2 可知 $\alpha(G^n)\le \phi(G^n)\le \phi(G)^n$, 開 $n$ 次方取極限便可以得到引理。 $\Box$

有了上述的基礎, 我們便能來看 Lovász 對於 $\psi(G)=\sqrt 5$ 的精彩證明。 考慮一把傘 (是的, 雨傘, 現實生活中的那個), 其傘柄跟傘骨均為單位長, 而傘骨有五根, 並想像傘的頂端位於三維空間中的原點 $O$(0,0,0), 傘柄的一端在 (0,0,1), 而五根傘骨的一端 $A_1,A_2,A_3$, $A_4,A_5$ 在傘是合著的時候, 也是在 (0,0,1)。 當我們打開這把傘的時候 $A_1,A_2,A_3,A_4,A_5$ 落在三維空間的平面 $z=\sqrt{1-r^2}$ 中以 $(0,0,\sqrt{1-r^2})$ 為圓心及 $r$ 為半徑的圓上, 形成一個正五邊形。 $r$ 從 0 逐漸增大到最多為 1 就是打開傘的過程。 當半徑為 $r$ 時, 正五邊形的邊長為 $2r\sin 36^\circ$, 而不相鄰的 $A_i$ 和 $A_j$ (例如 $A_1$ 和 $A_3$) 之間的距離為 $2r\sin 72^\circ$, 所以傘骨 $OA_i$ 和 $OA_j$ 形成邊長為 1、 1、$2r\sin 72^\circ$ 的等腰三角形, 由畢氏定理得知 $OA_i$ 和 $OA_j$ 的夾角在 $2r\sin 72^\circ=\sqrt{2}$ 時為直角, 也就是說, 傘打開到 $r=\csc 72^\circ/\sqrt{2}\approx 0.7435$ 時, 不相鄰的骨之間的夾角恰為直角, 此時我們就把傘柄對應的向量當作 $c$, 而傘骨對應的向量 $u^1,u^2,u^3,u^4,u^5$ 就會是 $C_5$ 一組標準正交代表。 可以計算 $\langle c,u^i\rangle=5^{-1/4}$, 從而 $\psi(C_5)\le \phi(C_5)\le \sqrt 5$, 故得到 $\psi(G)=\sqrt 5$。

參考文獻

---本文作者任教國立台灣大學數學系---