# Finite Playground

## 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$).

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

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

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).

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 會有問題), 證明完成.

## A lower bound to Ramsey numbers and an application

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

$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)$.

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$.  整理不等式便得出我們的結果.

## Maximum matching in general graphs

RandMatching(G), G 為 n-node m-edge graph.
1. 令$M_0$為任意 matching. 令$p = 2^m$.
2. 執行底下迴圈$k=10m \log n$次, 迴圈參數為$i$:
2.1 隨機選取一個邊$e$.
2.2 令$M'$$\frac{p}{1+p}$的機率是$M_i \cup \{e\}$, 有$\frac{1}{1+p}$的機率是$M_i \setminus \{e\}$.
2.3 假如$M'$是個 matching, 則令$M_{i+1} = M'$; 不然就還是讓$M_{i+1} = M_i$.
3. 輸出$M_k$, 程式結束.

## Random stuff, 110629

• Triangle detection
很久很久之前讀過的 triangle detection. 用到了弱化的$\epsilon$-net theorem.
結果: sub-cubic triangle detection 等價於 sub-cubic All-pair shortest path(!), 更 imply sub-cubic Boolean matrix multiplication(!!)
學習組合最優化 (combinatorial optimization) 與計算幾何 (computational geometry). 首先接觸的是 additive spanner 問題; S. Baswana et al. 的論文可以當作不錯的 survey.
簡單的學了 additive 6-spanner 的構造, 精神上就是 clustering.
結果: 任何圖會有個$O(n^{4/3})$-size additive 6-spanner. Sublinear-size $(1+\epsilon)$-multiplicative spanner 有多種構造法.
• Geometric set cover
然後就開始碰 geometric hitting set problem. 讀了 On the Set Multi-Cover Problem in Geometric Settings, 把 set multi-cover 問題 reduce 到一般的 set cover, 得到一個$O(\log \mathsf{opt})$-approximation 演算法. 而 set cover 一般來說只有標準的$O(\log n)$-approximation, 利用 bounded VC-dimension 配上$\epsilon$-net theorem (又是它!) 可以得到上面的 bound.
而對於 maximum coverage problem, 標準的解是個$1-1/e \approx 0.632$-approximation. 想要解所謂的 maximum 2-coverage problem, 也就是要 maximize 被蓋到兩次以上的點; 因為要 optimize 的函數喪失了 submodular 的性質, 因此目前沒有任何不單純的 upper bound.
• Girth on planar graphs
關於平面圖, 老師和我寫的 Computing the Girth of a Planar Graph in Linear Time 上了 COCOON’11. 一張圖的 girth 是指圖中最小圈的大小.
• Minimum cut on planar graphs
最近這個問題被解到$O(n \log\log n)$ time. 其中 C. Wulff-nilsen 用 r-division, multiple source shortest-path 與 fast Dijkstra 解掉了很多平面圖上的問題, 但經過近半年的嘗試, 似乎這是現在技巧的極限.
在 unweighted graph 上蛋蛋和我提出一個關於 planar distance preserver 的猜想, 不過仍然不知道怎麼處理.
• Diameter on planar graphs
現在嘗試改解 diameter problem. 一張圖的 diameter 圖中最長的 shortest path 的長度. 在 general graph 上人們相信這跟 All-Pair shortest path 一樣難, 但在平面圖上 C. Wulff-nilsen 可以解到$o(n^2)$, 因此說不定比較容易. 還在熟悉 diameter 的性質當中!
• Even/odd hole detection
努力的寫作 even hole detection 論文中, 目前的時間似乎是$O(n^{10})$. 總覺得分析越多結構結果會越好, 但論文複雜度就越高; 似乎是個可以很容易得到 lower bound 的問題? 但沒有看到人做過.
讀了 Odd Hole Recognition in Graphs of Bounded Clique Size, 技巧跟當初 P. Seymour et al. 的 even hole detection 差不多, 只是在 odd hole 上的結構較弱, 最主要的問題是 clique 大小可以很大!
然後讀了證明 odd hole through one node 是 NP-complete 的證明; 試著想要去掉那個一定要經過的 node, 還沒有完全看出問題所在. Odd hole detection 永遠會是目標之一!

(to be continued…)

## Linear algebra and Lagrange interpolation formula

$\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} }$,

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

$\displaystyle{ [x^i](\sum_{i=0}^n \beta_i x^i) = \beta_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) }$.

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

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

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

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

$\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} }$

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