Finite Playground

To verify is human; to prove, divine.

Leave a comment

Crossing number of Kn and Gioan’s Theorem

The Harary-Hill Conjecture states that the crossing number of complete graph Kn is

\displaystyle \frac{1}{4} \left\lfloor\frac{n\vphantom{-0}}{2}\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor \left\lfloor\frac{n-3}{2}\right\rfloor.

Instead of looking at all possible drawings (which is infinite), we can partition the drawings into classes, depending on the rotation system of the drawing.

The following theorem guarantees us that the crossing number is still well-defined.

Gioan’s Theorem.  Let D1 and D2 be two drawing of graph Kn in the plane.  Then one can transform D1 into Dusing only \Delta-moves.  As a corollary, the crossing number of D1 and Dis the same.

Noted that in general this is not true when the graph is not complete.


Leave a comment

Dilworth Theorem and equivalence to Konig-Egervary Theorem

Dilworth’s Theorem. If P is a finite poset, then the maximum size of an antichain in P equals the minimum number of chains needed to cover the elements of P.

Proof. Induction on |P|. We separate into two cases.

(a) Some maximum antichain A omits both a maximal element and a minimal element of P. Then neither D[A] or U[A] contains all of P; the maximality of A implies P = D[A] \cup U[A]. Both D[A] and U[A] has width w(P) because they contain A, and they only intersect in A. Apply induction hypothesis on both sets, we obtain k chains covering D[A] and k chains covering U[A]; combining these chains form k chains covering P.

(b) Every maximum antichain of P consists of all maximal elements or all minimal elements. Thus w(P-\{x,y\}) \le k-1 if x is a minimal element and y is a maximal element below x. Apply induction hypothesis on P-\{x,y\} gives us k-1 chains; add chain \{x,y\} to get a covering of P.

Theorem.  Dilworth’s Theorem is equivalent to Konig-Egervary Theorem.

Proof.  Dilworth to Konig-Egervary: View an n-node bipartite graph G as a bipartite poset. The nodes of one part are maximal elements, and nodes of the other part are minimal. Every covering of the poset of size n-k uses k chains of size 2, which is actually a matching. Each antichain of size n-k corresponds to an independent set in G, and the rest of k nodes forms a vertex cover.

Konig-Egervary to Dilworth: Consider an arbitrary poset P of size n. Define a bipartite graph G as follow: For each element x \in P, create two nodes x^- and x^+. The two parts of the graph are \{x^- : x \in P\} and \{x^+ : x \in P\}. The edge set is \{x^- y^+ : x <_P y\}.

Every matching in G yields a chain-covering in P as follow: We start we n chain, each contains a unique element. If x^- y^+ is in the matching then x and y are combined in the same chain. Therefore because each node in G appears in at most on edge of the matching, a matching of k edges forms a covering of n-k chains.

Given a vertex cover R in G of size k, define a corresponding antichain A = \{x \in P : x^-, x^+ \notin R\}; this is indeed an antichain because if there is a relation x <_P y in A then edge x^- y^+ will be presented, and vertex cover R needs to contain at least one of x^-, y^+.

Claim. No minimal vertex cover of G uses both \{x^-,x^+\}, because by transitivity the sets \{z^- : z \in D(x)\} and \{y^+ : y \in U(x)\} induce a complete bipartite subgraph in G. A vertex cover of a complete bipartite graph must use all of one part. Since x^-,x^+ have all the neighbors in these two sets, we can remove one of x^-,x^+ that is not in the right part and decrease the size of the vertex cover.

Thus a minimum vertex cover of size k yields an antichain of size n-k.

Leave a comment

Graph coloring theorems revisited II – Vizing’s Theorem

Alexandr Kostochka found the following new proof to the classical theorem.

Vizing’s Theorem.  For every simple graph G, \chi'(G) \le \Delta(G) + 1.

Proof.  We prove by contradiction; assume that G is a minimal counter-example (in terms of number of edges) to the statement; that is, G has no edge-(\Delta+1)-coloring.

Let \phi be an edge-(\Delta+1)-coloring of G-xy. For every v \in V(G), let O(v)=O_\phi(v) denote the set of colors in [\Delta+1] not used to color the edges incident to v; one can see that O(x) \cap O(y) = \emptyset.

Construct the auxiliary multidigraph H as follows: V(H) = N_G(y) and there is a directed edge from u to v in E(H) if \phi(vy) \in O(u). Intuitively an edge from u to v means that if we can recolor vy, then we can recolor uy as well. Let X be the set of vertices reachable in H from x (x \in X as well); any recoloring of an edge wy for w\in X will imply that we can color xy. Since the out-neighbors of a vertex reachable from x also are reachable from x, N^+_H(v) \subseteq X for every v \in X.  Therefore

\sum_{v \in X} d^+_{H[X]}(v) = |{E(H[X])}| = \sum_{v \in X} d^-_{H[X]}(v) \text,

and the theorem will be proven if we can show that

  1. d^+_{H[X]}(v) \ge \Delta - d(v) + 1 + [v = x] and
  2. d^-_{H[X]}(v) \le 1-[v=x] for all v \in X;

this implies

0 = \sum_{v \in X} \{d^+_{H[X]}(v) - d^-_{H[X]}(v)\} \ge 2 + \sum_{v \in X} (\Delta - d(v)) \ge 2,

a contradiction.  Items (1) and (2) follow from the following claims. Let \alpha \in O(y).

Claim 1 (Exchange argument).  \alpha\notin O(v) for every v\in X.
Proof sketch.  Recolor the edges of the form wy for each w on the path from x to v.

Claim 1 yields that for every v \in X and \beta \in O(v), there is some w \in N(y) with \phi(yw)=\beta. Then by the definition of H, vw\in H[X]. Because |{O(v)}| \ge \Delta+1-d(v) for each v\in V(G) and |{O(u)}| \ge \Delta+1-d_{G-xy}(u) = \Delta-d(u)+2 for u \in\{x,y\}; so

d^+_{H[X]}(v) \ge \Delta+1-d(v) for every v \in X and d^+_{H[X]}(x) \ge \Delta-d(x)+2.

Claim 2 (Distinct O-sets).  For all distinct v,w \in X, O(v) \cap O(w) = \emptyset.
Proof sketch.  A [\beta,\gamma]-path in G is a path whose edges are alternately colored with \beta and \gamma. A [\beta,\gamma](a,b)-path is a [\beta,\gamma]-path from a to b in G.

Claim: If v \in X and \beta \in O(v), then G contains an [\alpha,\beta](v,y)-path.  The claim follows from a Kempe-chain-like argument to recolor vy with \alpha.

Then suppose there are v,w\in X with \beta\in O(v)\cap O(w), then the [\beta,\alpha]-path starting at y must end at both v and w, a contradiction.

Claim 2 yields that d^-_{H[X]}(v) \le 1 for every v \in X and d^-_{H[X]}(x) = 0, because the color on edge vy corresponds to a unique in-neighbor of v (and there are no color on edge xy).

Leave a comment

Graph coloring theorems revisited I – Brook’s Theorem and Rubin’s Block Theorem

這學期在修學校著名的組合數學課程, 課本當然是使用 Douglas B. West 的新書草稿.  其中有許多內容是全新的, 我想這會成為新一代的組合學以及圖論教科書吧?

今天要談的是圖著色中著名的定理之一 — Brooks’ Theorem, 說明只要不是完全圖或奇圈 (odd cycle), 我們便可以稍稍改進單純的上界 \Delta(G) +1\Delta.  但當初學到的證明簡直是魔術, 看不出什麼東西.  在 West 的新書中使用了 [Entringer85] 的結果, 說明為何這兩種圖比較特別.

Rubin’s Block Theorem.  令 G 為一雙連通圖; 若 G 不是完全圖或奇圈, 則 G 中有一個含有最多一條弦 (chord) 的偶圈.

很奇怪的圖結構定理, 但我們來看看要怎麼使用它!  定義圖 G 為 degree-choosable 如果對於任意的色組函數將每個圖中的點對應到一組可選擇的顏色, 且每個點上的顏色至少跟點的 degree 相同, 我們都保證可以從每組顏色中選取一種將圖適當的著色.  底下這兩個 Lemma 不難證:

Lemma 1.  給定連通圖 G 與一色組函數 L, (i) 若有某個點 v 的顏色選擇多於 degree, 則圖 G 可順利著色; (ii) 若圖 G 為雙連通, 且有兩個點上的顏色組不同, 則圖 G 可順利著色.

Lemma 2.  連通圖 G 若存在一 degree-choosable 生成子圖 H, 則圖 G 也是 degree-choosable.
Proof.  By Lemma 1(a).

利用 Lemma 1,2 與 Rubin’s Block Theorem 我們可以證明底下的若且唯若條件, 不過我們只需要唯若方向就是; 所以暫時先證一邊!

Theorem.  圖 G 不為 degree-choosable 若且唯若每個雙連通集 (block) 皆為完全圖或奇圈.
Proof.  由 Lemma 2 與 Block Theorem 我們只需要證明含有最多一條弦的偶圈是 degree-choosable; 但利用 Lemma 1(b) 這很明顯.

Brooks’ Theorem (extended).  若圖 G 不是完全圖或奇圈, 則 \chi_{\ell}(G) \le \Delta(G).
Proof.  利用上面的 Theorem 我們只需要處理當所有雙連通集都是完全圖或奇圈的情形.  如果有個點的 degree 比 \Delta(G) 小, 利用 Lemma 1(a) 就結束了; 所以 G 一定是 \Delta(G)-正則 (regular); 但在這種情況下表示我們只有一個 block (不然斷點的 degree 會有問題), 證明完成.

不過, 這其實不是我最喜歡的證明; degree-choosable 的部分可以被另一個定理取代, 並且能更增強證明的結果; 我們留到下次再介紹 Alon-Tarsi Theorem.

Leave a comment

A lower bound to Ramsey numbers and an application

Ramsey’s Theorem.  R(p_1,\ldots,p_k;r) is finite.

常看見的證明是先證 r=2 的情形 (r=1 當然是鴿籠原理), 然後再對 r\sum p_i 作兩變數歸納法; 證明底下的不等式就完成了.

R(p_1,\ldots,p_k;r) \le R(p_1',\ldots,p_k';r-1)+1, where p_i' = R(p_1,\ldots,p_{i}-1,\ldots,p_k;r).

當然R(p,p) := R(p,p;2)仍是我們最關注的; 底下的機率方法可以證明一個簡單的下界.

Theorem. R(p,p) = \Omega(p 2^{p/2}).
Proof.  每個特定的p-clique 或p-independent set 出現的機會都是2^{-{p \choose 2}}; 因此若2{n \choose p} 2^{{n \choose 2}-{p\choose 2}} < 2^{n \choose 2}的話就表示某個大小為n的圖同時沒有大小為p的 cliques 或 independent sets, 因此R(p,p) > n.  整理不等式便得出我們的結果.

這個下界告訴我們一個大小為n的圖會有個O(\log n)大小左右的 clique 或 independent set.  但有趣的地方是我們可以用類似的方式證明不會有太大的C_4-免除生成子圖.  證明如下: 大小為p的生成子圖數量為n^p; 每張生成子圖最多有{p \choose 2}條邊.  我們可以將這些潛在邊分解成\Omega(p^2)個邊互斥的K_4(why?), 而每個K_4是個真正C_4的機率是6/2^6, 因此我們可以保證每個大小為p的生成子圖是C_4-免除的機會不會超過c^{p^2} (c < 1).  套用聯集上界 (union bound) 便完成了.

這告訴我們, 如果要在圖中找個大小為O(\log n)左右的C_4-免除生成子圖 (例如想要找個 inteval graph 或 chordal graph), 不如就找完全集或獨立集算了, 反正放寬條件也找不到更大的.

我們同時可以觀察到將大小為 n 的完全圖分解成大小為 k 的小完全集這件事其實就是找一個 t=2 的 partial Steiner system S(n,k,t); 利用所謂的 Erdos-Hanani-Rodl 定理 (原本是 Erdos-Hanani 猜想), 我們知道對於任意的 n,k,t 存在著大小大約為{n\choose t}/{k\choose t}的 partial Steiner system.  因此上述所說的C_4 並沒有什麼特別的; 我們可以證明對於任意大小為 k (常數) 的圖 H, 存在大小為 n 的圖 G, 其中 H-免除生成子圖的大小大約是\Theta(\log n).  同樣的定理可以推廣到 hypergraphs!  這一屆當然都符合 Ramsey 理論 (事實上, 就是隨機性) 的精神: 只要結構夠大, 裡頭什麼事都會發生, 就算是規律; 想要避免某一種規則的產生是不可能的.


Linear algebra and Lagrange interpolation formula

最近在重讀線性代數, 對這門科目有了些新的認識!
前幾天讀到 dual space and dual basis, 發現高中時整天在算它的行列式, 卻一直不知道有什麼用處的 Vandermonde 矩陣:

\displaystyle{  A = \begin{bmatrix}  \alpha_0^0 & \alpha_0^1 & \cdots & \alpha_0^n \\  \alpha_1^0 & \alpha_1^1 & \cdots & \alpha_1^n \\  \vdots & \vdots & & \vdots \\  \alpha_n^0 & \alpha_n^1 & \cdots & \alpha_n^n  \end{bmatrix}  },


考慮一個體F上的n+1維向量空間V, 令V^* = L(V,F)為其對偶空間, 也就是那些從V打到F的線性函數所形成的向量空間. 令B = (e_0,\ldots,e_n)V的一基底, 則我們在V^*中會有對偶基底B^* = (e^0,\ldots,e^n), 滿足

\displaystyle{  e^j e_i = [i = j]  },

其中[i=j]值為1如果i=j, 不然就是0. 可以想像基底跟對偶基底只要是不同國 (不同 index) 就會 “相殺”, 這樣就好想多了.

用一些例子來看這個對偶基底: 令F=\mathbb{C}為複數, V=F^{\leq n}[x]為所有係數為複數的n次多項式所形成的向量空間. (檢查!) 這時我們會發現V的維度是n+1, 也就是說基底大小會是n+1. 按照我們對多項式的 “直覺”, 應該會猜B = (x^0,\ldots,x^n)是一組V的基底. (的確如此!) 那麼跟它對應的對偶基底是誰呢? 應該要是那些能滿足相殺性質的線性函數. 令B^* = ([x^0],\ldots,[x^n]), 其中[x^i] : V \to F是取多項式中x^i項係數的函數(因此[x^i]\in V^*); 也就是說對於某個V中的多項式f(x) = \sum_{i=0}^n \beta_i x^i,

\displaystyle{  [x^i](\sum_{i=0}^n \beta_i x^i) = \beta_i  }.

因此,BB^*滿足相殺性質, 所以取係數函數B^*B的對偶基底.

而除了取係數函數, 我們還有什麼在V上很自然的線性函數呢? 當然就是取值函數了: 我們隨便取n+1個不一樣的複數(\alpha_0,\ldots,\alpha_n), 令B_L^* = ([\alpha_0],\ldots,[\alpha_n]), 其中[\alpha_j] : V \to F是將多項式中所有x代入\alpha_j的函數; 因此對於某個V中的多項式f(x) = \sum_{i=0}^n \beta_i x^i,

\displaystyle{  [\alpha_j](f(x)) = [\alpha_j](\sum_{i=0}^n \beta_i x^i) = \sum_{i=0}^n \beta_i \alpha_j^i = f(\alpha_j)  }.

我們可以證明B_L^*是個V^*中的基底. 那麼它的對偶基底應該要是誰呢? 為了要滿足相殺性質, 經過一陣努力後我們發現應該是底下這組多項式. 令B_L = (L_0(x),\ldots,L_n(x)), 其中

\displaystyle{  L_i(x) = \prod_{j=0 \atop j \neq i}^n \frac{x-\alpha_j}{\alpha_i-\alpha_j}  }.

我們稱這些多項式為 Lagrange 多項式. 它們擁有的性質, 正好就是當你將\alpha_i帶入這些多項式時, 會滿足

\displaystyle{  [\alpha_j]L_i(x) = L_i(\alpha_j) = [i = j]  }

這樣的相殺性質! 因此我們知道 Lagrange 多項式B_L是取值函數B_L^*的對偶基底.


我們要怎麼證明 Lagrange 多項式B_L的確會是V的一組基底呢? 他們不像B = (x^0,\ldots,x^n)看起來這麼和藹可親; 不過, 根據對偶基底的性質, 我們有以下等式: 對於V中的任意多項式f,

\displaystyle{  f = \sum_{i=0}^n (e^i f) e_i  }.

因此在我們的例子中, 我們將f依序代入所有B基底中的x^j:

\displaystyle{  x^j = \sum_{i=0}^n ([\alpha_i]x^j) L_i(x) = \sum_{i=0}^n \alpha_i^j L_i(x)  },

我們發現這是一組線性方程, 也就是一個從B_LB的線性變換. 將這個線性變換寫成矩陣的形式, 我們很驚訝的發現這個矩陣恰巧就是Vandermonde 矩陣!!

\displaystyle{  A = \begin{bmatrix}  \alpha_0^0 & \alpha_0^1 & \cdots & \alpha_0^n \\  \alpha_1^0 & \alpha_1^1 & \cdots & \alpha_1^n \\  \vdots & \vdots & & \vdots \\  \alpha_n^0 & \alpha_n^1 & \cdots & \alpha_n^n  \end{bmatrix}  }

而我們高中時計算 Vandermonde 矩陣的行列式值不為零, 完全就是在說這個線性變換是個V上的自同構映射 (automorphism), 而B_L的的確確是個基底. 我們稱這組線性方程為 Lagrange 插值公式 (Lagrange interpolation formula), 它的用途在於能夠回答底下這個問題:

給定兩組n+1個不一樣的複數(\alpha_0,\ldots,\alpha_n)(\beta_0,\ldots,\beta_n), 求一個n次多項式f滿足f(\alpha_i) = \beta_i.

要怎麼得到這個多項式f呢? 若是用基底B來思考就會很困難, 但改用基底B_L, 很容易我們就可以看出令

\displaystyle{  f(x) = \sum_{i=0}^n \beta_i L_i(x)  }


原以為故事到這裡就告一段落了, 沒想到在看後面的矩陣對角化時, 前面說的事情可以帶來更新一層的感受… 待續!!

Leave a comment

Isolation Lemma


這段時間在學習一個好用的技巧 – Isolation Lemma. 當我們需要在一個圖中找到特定的結構 (例如一個 perfect matching), 有時直接去找不是那麼容易; 藉由孤立 (isolation) 出某一個特定的 minimum weighted matching, 我們就能很快的找到它. 最有名的使用就是在 [MVV87] 中 Mulmuley, Vazirani 和 Vazirani (你沒看錯) 藉由證明了最初 Isolation Lemma 的雛形而得到的 perfect matching\mathsf{NC}(平行) 演算法.

在此我們介紹兩種不同的改良版: 一種是後來被 [RA00] 使用, Reinhardt 和 Allender 證明了\mathsf{NL/poly} = \mathsf{UL/poly}; 此種方法的特點是得到的 bound 很好, 但是是非建構式的. 而另一種類似 hash 的方式則是被 [CRS93] 使用, 改進了當初 [MVV87] 的演算法而得的\mathsf{NC^2}perfect matching 演算法; 後面這種方法 weight 是建構式的, 可以直覺的看出為何它能夠把所有東西分開, 但是要用到少許的 randomization. (嚴格來說, 我們真正要使用第一種方式時, 還是有 randomized 的精神在裡頭.)

首先我們來看第一個形式的 Isolation Lemma.

Theorem 1.U為一大小為n的集合, 而\mathcal{F}_1, \ldots, \mathcal{F}_m為一族非空集合, 其中每一\mathcal{F}_iU的子集所形成的集合. 令d為重量的上限, 而W為所有重量不超過d的重量函數w: U \rightarrow [d]^n形成的集合. 若我們給定一參數0 < \alpha < 1使得\alpha > mn/d, 則至少有(1-\alpha)|W|的重量函數會使得每個\mathcal{F}_1, \ldots, \mathcal{F}_m中正好都只有一個最小重量的U子集.

看起來很複雜. 我們令m=1, d=2n\alpha = 1/2來觀察這個定理看看.

Theorem 1′.U為一大小為n的集合, 而\mathcal{F}為一非空集合, \mathcal{F}中每一元素為U的子集. 均勻獨立的在U上隨機給定[2n]內的重量. 則至少有1/2的機率會使得\mathcal{F}中正好只有一個最小重量的U子集.

這樣就好懂多了; 藉由隨機給定一些不大的重量, 很容易能夠使得\mathcal{F}中有個最小元素被孤立出來. 如果不要限制重量的大小, 這其實不是很困難; 只要對U中的元素u_1, \ldots, u_n分別給予重量2^1, \ldots, 2^n就行了. 不難根據二進位表示看出U中的元素都會有不同的重量. 重點在於, 這樣的重量是指數成長的, 而多數演算法的應用只能限制在多項式成長率下. 這時藉由一點點的隨機性, 就能夠達成這樣的目標, 這是 Isolation Lemma 的厲害之處!

來看一個實際的例子好了. 在 [RA00] 的證明當中, 他們用 Isolation Lemma 孤立出圖中某兩點之間的某條路徑. 因為對任意圖來說兩點間的路徑最多會有 exponential 那麼多, 所以我們需要借助 Isolation Lemma.

[p]為圖中的點集, U為圖中的邊集, \mathcal{F}_i為點1到點i所有路徑的集合. (注意我們將路徑視為邊集的子集.) 因為|U| = n = p(p-1)(有向邊), 我們令m=p, \alpha = 1/2, d=2p^3 > mn/\alpha. 因此根據 Theorem 1, 我們可以證明底下的推論:

Corollary.G為一p點有向圖, 而W為所有重量函數w: E(G) \rightarrow [2p^3]^n形成的集合. 則至少有|W|/2的重量函數會使得對於所有i, 點1到點i的最小重量路徑是唯一的.

為什麼需要這麼多的重量函數呢? 因為我們可以藉此證出更厲害的推論:

Corollary.W為所有重量函數w: E(G) \rightarrow [2p^3]^n形成的集合. 則存在w_1, \ldots, w_{p^2} \in W個重量函數會使得對於所有p點有向圖G, 一定有一個w_k使得在G種任意點1到點i的最小重量路徑是唯一的.

Proof. 對任意一張圖, p^2個重量函數都無法估立出最短路徑的機率是2^{-p^2}. 而p個點的有向圖共有2^n = 2^{p(p-1)}個, 因此p^2個重量函數都無法孤立出某一張p點有向圖的最短路徑的機率是

2^{-p^2} \cdot s^{p(p-1)} < 1,

因此存在某個重量函數不管什麼樣的p點有向圖都能夠孤立出其最短路徑. \Box

注意後面這個推論的重點: 那p^2個重量函數是對所有p點的有向圖都適用的, 因此我們可以把這些重量函數事先寫進程式當中, 每當輸入一個圖我們就拿其中一個重量函數來孤立出最短路徑. 如果不使用這種方式, 我們就要在程式執行過程中隨機的產生一些重量函數, 給定了一個圖, 我們需要

n\log p = O(p^2 \log p)

個 random bits 來產生一組重量函數.


前面提到如果不限制重量的大小, 只要對U中的元素給予重量2^1, \ldots, 2^n就好了. 第二個方法利用中國剩餘定理很輕易的將重量作一些改變而壓在多項式大小, 因此這樣的方法式建構式的. 我們回到只有一個\mathcal{F}的狀況, 這次我們利用\mathcal{F}內子集的數量來減少 random bits 的使用.

Theorem 2.U為一大小為n的集合, 而\mathcal{F}為一非空集合, \mathcal{F}中每一元素為U的子集. 存在一種使用O(\log|F| + \log n)個 random bits 的方式在U上給定[n^7]內的重量, 使得至少有1/4的機率會使得\mathcal{F}中正好只有一個最小重量的U子集.

最糟糕的狀況下|F| = 2^n, 因此使用的 random bits 會是O(n + \log n), 比前一種方法好; 當|F|更小的時候 (如|F|是多項式大小), 我們甚至只需要至多$latex O(\log n)$ bits 就夠了. 完整的證明請見 [CRS93]. 不過事實上如果|F|只有多項式大小, 我們其實可以連 random 都不要用! 這在 [PTV10] 裡被拿來用以證明\mathsf{RFewL} \subseteq \mathsf{UL}, 管它這兩個莫名其妙的東西是什麼.

Theorem 2′.U為一大小為n的集合, 而\mathcal{F}中有至多f(n) = O(n^c)U的子集S_1, \ldots, S_{f(n)}. 存在一種在U上給定多項式大小的重量, 使得\mathcal{F}中正好只有一個最小重量的U子集.

Proof. 首先我們給U中的每個元素u_i重量2^i. 然後我們來看底下這個多項式:

\Delta = \prod_{1 \leq i < j \leq f(n)} (w(S_i) - w(S_j)),

這個多項式的特色就是: 當重量函數w能讓所有\mathcal{F}中的元素重量都不一樣時, 這個判別式\Delta就會不為零. \Delta值的範圍會是\delta = (2^{n+1})^{f^2(n)}. 因此我們選出從2開始的s個質數p_1, \ldots, p_s, 使得它們相乘超過\delta = (2^{n+1})^{f^2(n)}. 換句話說,

\Delta \neq 0 \mod \prod_{i=1}^s p_i.


\log \prod_{i = 1}^s p_i = s + o(s) > \log \delta = (n+1)f^2(n),

f(n) = O(n^c)時我們只要有s = n^{2c+1}就夠了. 這時中國剩餘定理告訴我們, 因為\Delta \neq 0 \mod \prod_{i=1}^s p_i, 所以一定有一個p_i使得\Delta \neq 0 \mod p_i. 最後我們只要令新的重量函數為w^*(S) = w(S) \mod p_i就行了, 根據對質數大小的估計,

p_i \leq p_s \leq s\log s \leq n^{2c+2},

因此這個重量函數只有多項式的大小而已. 因為\Delta \neq 0 \mod p_i, 所有\mathcal{F}中的元素重量都不一樣, 滿足我們對定理的需求. \Box

最後有一些後記. Isolation Lemma 使用上需要 randomized, 因為\mathcal{F}在最糟的狀況下會有2^n個元素, 因此完全的 derandomized 是不可能的. 不過針對\mathcal{F}的特性 (例如前面舉的最短路徑的例子), 有些人致力於 derandomize 相關的結果, 也有不少成果. 希望未來能看到 Isolation Lemma 更多的應用!

[MVV87] Matching is as easy as matrix inversion. K. Mulmuley, U. Vazirani and V. Vazirani.
[CRS93] Randomness-optimal unique element isolation, with applications to perfect matching and related problems. S. Chari, P. Rohatgi and A. Srinivasan.
[RA00] Making nondeterminism unambiguous. K. Reinhardt and E. Allender.
[PTV10] On the power of unambiguity in logspace. A. pavan, R. Tewari and N. V. Vinodchandran.