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 理論 (事實上, 就是隨機性) 的精神: 只要結構夠大, 裡頭什麼事都會發生, 就算是規律; 想要避免某一種規則的產生是不可能的.

Leave a comment

Shortest paths in graphs with integral weights

發現每次寫文章都因為希望講完整, 寫的很長因此很花時間, 久了就開始懶了.
因此, 新增一個 “速記” 分類, 用來記錄一些想要寫下來但不想整理的東西 XDD

目前看到在 integral weights 上解 Shortest paths 的方法有:
Thorup ’03, directed graphs, O(m + n \log\log n), by integral priority queue
Thorup ’99, undirected graphs, O(m), by hierarchical bucketing.

如果有最大的邊重 C, 那麼
van Emde Boas ’77, O(m \log\log C),
Thorup ’03, O(m + n \log\log C).

Survey: Zwick ’01.