[Graph Theory] Probabilistic Method

와 이젠 진짜 하나도 모르겠다...

한계가 왔다...

 

9.1. Basic probabilistic method

 

Definition.

descrete probability space: 유한하거나 가산인 set $S$ 와 function $P$ 로 정의된 subsets of $S$ <event> 에서

$A \subseteq S$ 면 $0 \leq P(A) \leq 1$ 이다.

$P(S) =1$ 이고

$A_1, A_2, ..., $가 $S$의 pairwise disjoint subset이라면, $P(\cup A_i) = $\sum_{i=1}^{\infinity}P(A_i)$ 다.

 

Theorem <Erdos>

$R(k, k) > \frac{k2^{k/2}}{e\sqrt{2}}

$\textit{Proof}$

잘은 모르겠는데, $K_n$짜리 그래프의 edge 를 빨강/파랑으로 색칠한다 치면 확률이 1/2니까

일단 $\binom{n}{2}$개의 edge가 있다는 뜻이고,

$k$ 개의 vertices 가 같은 색일 확률은 $2 \times 2^{-\binom{k}{2}}$ 가 나온다.

총 $\binom{n}{k}$개의 event가 발생하니, 최소 하나의 색에서 그런 일이 발생할 확률이 최대 $\binom{n}{k}2^{1-\binom{k}{2}}$ 가 나온다는 거.

이게 1보다 작으면 size k짜리 homogeneous set 이 없이 2-edge-coloring 이 된다는 뜻이니까 $R(k,k) > n$ 이 됨.

$\binom{n}{k} < (\frac{ne}{k})^k$ 니까 $\frac{ne}{k} \leq 2^{(k-1)/2}$ 가 나와서 결국

$n \leq \frac{k2^{k/2}}{e\sqrt{2}} 가 나온다.

 

Definition.

Hypergraph $H$ 의 proper k-coloring: $k$ 개의 color set을 가지고 $H$의 아무 edge 도 monochromatic 하지 않게 $V(H)$ 의 labeling 을 성공할 때.

A hypergraph is k-colorable: proper $k$ coloring of $H$

 

Proposition <Erdos>

$f(k)$ 가 2-colorable하지 않은 k-uniform 하이퍼그래프의 최소 edge 갯수라면,

$2^{k-1} \leq f(k) \leq \binom{2k-1}{k} \sim \frac{4^k}{\sqrt{\pi k}}$

$\textit{Proof}$

랜덤하게 2 색으로 edge를 칠할 때,

어떤 edge 가 monochromatic 할 확률은 $2^{1-k}$ 고,

그러니 $2^{k-1}$ 개보다는 적은 edge 가 그런 나쁜 일이 일어날 확률이 1보다 적어서 proper 2-coloring 이 존재한다.

Pigeonhole principle 에 의해 edge set $\binom{[2k-1]}{k}$ 짜리 hypergraph 가 non 2-colorable 이다. 왜냐하면 어떤 $k$ 개 vertex 들은 같은 색을 가져야만 하니까. 마지막 $frac{4^k}{\sqrt{\pi k}}$ 변환은 Stirling formula로 나오는거래.

 

Theorem <Erdos>

$(1 + o(1))\frac{e \ln 2}{4}k^22^k$ 개의 edge 짜리 k-uniform hypergraph 은 2-colorable하지 않다.

$\textit{Proof}$

$m$ edge랑 vertex set [n] 짜리 k-uniform hypergraph 를 생각해봐.

$r$ 개를 한 색으로, $s$개르 ㄹ다른 색으로 칠하면 random $k$-set이 monochromatic 할 확률은

$\frac{\binom{r}{k} + \binom{s}{k}}{\binom{n}{k}}$ 다.

그리고 저 확률은 $r=s=n/2$일 때 최소가 됨. 왜냐면 $\binom{x}{k}$ 는 x에 대한 convex function 이니까.

coloring $\sigma: [n] \rightarrow \{0, 1\}$ 을 생각해봤을 때, $[n]$의 random 한 $k$-subset 이 monochromatic 할 확률은 최소 $2 \binom{n/2}{k}/\binom{n}{k} =: p$ 다.

이 뒤는 솔직히 못알아먹겠으니까, 사실 아까부터 못알아먹었지만, 나중에 쓰겠다.

 

Theorem

$n_k$ 가 non-k-choosable bipartite graph 의 smallest order일 때, $f(k) \leq n_k \leq 2f(k)$이다.

 

9.2. Random variables and expectation

일어나선 안될 bad event 를 정해놓고, 그 bad event 가 없을 확률이 양수다! 라는 컨셉의 probabilistic method 의 기초적인 접근. 그럼 bad event 가 쪼끔은 괜찮고, 많지만 않으면 된다라면? bad event를 피하는 것 자체가 아니라 갯수를 세고 싶을 때. 최대 또는 최소 몇 번 일어나느냐? 에 포커스를 맞춰보자.

 

Definition

Random varible: Discrete probability space $S$ 에서 정의된 function $X$. RV는 함수임!!

The range of random variable: 별 말 없을 때에는 실수 $\mathbb{R}$ 이고, 

Discrete random variable: range 가 $\mathbb{N}$

Indicator random variable: range 가 $\{0, 1\}$

$X = k$: event $\{a \in S: X(a) = k\}. $X$의 결과가 $k$가 나오게 하는 $S$ 상의 event들.

$Pr(X=K)$: $X$가 $k$가 나올 확률

Expectation, $\mathbb{E}[X]$: $\sum_{a \in S} X(a)Pr(a)$, 합이 수렴할 때.

 

Fact.

어떤 $\mathbb{E}[X]$를 생각해봐. 이게 나왔다는 건, 어떤 $X(a)$ 가 이 값에 얼추 비슷하게 (as large as, as small as) 있다는 거야.

 

Lemma <Linearity of expectation>

$X, X_1, ..., X_k$ 가 $X = \sum X_i$ 인 same space 상에 정의된 Random variable 들이라면,

$\mathbb{E}[X] = \sum \mathbb{E}[X_i]$, also $\mathbb{E}[cX] = c \mathbb{E}[X]$ 다.

 

그러니, 만약 $X_i$ 가 indicator rv면, $\mathbb{E}[X_i] = Pr(X_i = 1)$ 이라는 뜻이다. 이 원리로 list chromatic number 의 lower bound 를 증명할 수 있는데, proper coloring 이 발생하지 않는 경우를 고려해보자.

 

Theorem <Alon>

average degree 가 $d$ 인 모든 $G$ 에 대해 list chromatic number of $G \geq c \frac{\log{d}}{\log{\log{d}}}$

$\textit{Proof}$

일단 $G$ 의 average degree가 $d$니까, minimum degree가 최소 $d/2$인 subgraph $G'$이 있다. <???>

$d_H(v) \geq d_{G'}(v)$ 인 spanning bipartite subgraph $H$가 $G'$ 안에 있고, 그러니까 $\delta(H) \geq d/4$다.

$H$에 대해서 size $s$ 짜리 리스트 $L$을 만들어보자. $H$의 bipartite set이 $A, B$고 큰 쪽을 $A$라고 하자. $S = [s^4]$인 $S$를 생각하고, $t = \binom{s^4}{s}$ 를 생각하자.

$B$의 각 vertex 에 $S$ 의 random $s$-subset 을 할당하고, 이러면 총 $t$개의 set들이 생긴다.

이 때 $A$의 각 vertex 가 $t$ 개의 list 들로 적절히 색칠되었다고 치자.

어떤 $s$짜리 set인 $T$ 가 neighbor에 등장하지 않을 확률은 $(1-1/t)^{d_H(x)}$ 다.

그러한 set 이 $t$개 있고, $d/4 > tlog(2t)$니까,

$Pr(x \textit{ is not full}) \leq t(1-1/t)^{d/4} < te^{-d/(4t)} < te^{-\log{(2t)}} = 1/2$

x의 친구들이 죄다 나올 수 있는 s개 조합 리스트들을 다 썼다! 이러면 full 인데, 안 full일 확률이라는게 $(1-1/t)^{d_H(x)}$ 이게 S개 조합 리스트 갯수(t)만큼 있어서 $t(1-1/t)^{d_H(x)}$ 가 되고, degree와 t의 관계를 계산하면 위와 같다.

$X$가 full vertices의 갯수니까, $\mathbb{E}[X]$ 는 최소 $|A|/2$가 되고, 최소 $|A|/2$개 이상의 vertices 가 full 이라는 결과임.

그럼 우리는 no proper coloring 이 선택되는 list assignment 의 확률이 positive probability 라는 접근을 써볼 거야. 

$f$ 가  $B$의 색상 choice라고 치자. A의 full vertex 들에 대해서 모든 $s$짜리 set 이 neighbor에 나오는 거니까, 최대 $s-1$ 개의 색은 neighbor에서 선택되지 않는다는 뜻. $f$가 x로 적절히 extend 되는 건, $L(x)$ 중에 mixxing color가 있을 때 나오는 것.

usable color를 이름 붙이는 데에 최대 $s-1$개의 방법이 있으므로, $L(x)$는 남은 색상으로 채워진다.

$Pr(x \textit{ can be colored }) \leq \frac{(s-1)\binom{s^4-1}{s-1}}{t} = \frac{s-1}{s^3} < \frac{1}{s^2}$

$f$를 $L$-coloring 으로 늘리기 위해서, 모든 full vertices 들이 색칠되어야 하고, 그 확률은 $(1/s^2)^{|A|/2}$ 로 bound 되고, 이건 $s^{-|A|}$ 랑 같다. B의 $f$ coloring 은 $s^{|B|}$ 의 선택지가 있으므로, $B$의 색상 초이스는 $s^{|B|}s^{-|A|}$ 가 되고. $|A| \geq |B|$ 니까, 이 bound 는 1보다 작다.

그러므로, 이런 list로 proper coloring 이 불가능한 assignment 가 존재한다.

 

나중에 Alon 은 이것을 $(\frac{1}{2}-o(1))\ln{d}$ 로 개선했다.

 

Proposition

$\binom{n}{k} \leq (\frac{ne}{k})^k$ and $1 + x \leq e^x$ for all x

 

9.3. Alteration Method

완전히 random 한 object를 만드는 게 아닌, 어느 정도 구상된 object 를 만들어놓고, deterministic 한 way 로 desired property 를 만들어내는 과정을 포함하는 것.

 

Theorem

$R(k,k) > (1-o(1)) \frac{k2^{k/2}}{e}$

$\textit{Proof}$

$X$ 가 $K_n$ 의 edge 를  2-coloring하는 과정에서 나오는 monochromatic $k-clique$ 의 갯수라고 하자.

Then, $C$ 가 모든 k-vertex subset of $V(K_n)$에 대해 그게 monochromatic 이면 1, 아니면 0 인 indicator 라고 했을 때, $X = \sum_CX_C$다.

$\mathbb{E}[X] = \sum_C \mathbb{E}[X_C] = \sum_C Pr[X_C = 1] = \binom{n}{k}2^{1-\binom{k}{2}}$

이 bound 를 maximize 할 수 있는 $n$을 찾아보자. 이걸 미분하면 $1 = k \frac{e}{k} (\frac{ne}{k})^{k-1}2^{1-k(k-1)/2}$가 나오니까, $n = e^{-1}k2^{k/2}(2e)^{-1/k}$ 다. $(2e)^{-1/k}$ 부분은 $k$가 크면 $(1+o(1))$ 이 된다.

$n$ 이 $e^{-1}k2^{k/2}$ 에 가까운 정수라고 했을 때,

$n-(\frac{ne}{k})^k2^{1-\binom{k}{2}} \geq \frac{1}{e} k 2^{k/2}(1-\frac{2e}{k})$

k가 커지면 $2e/k$ 가 0에 수렴하므로, 얘기했던 bound를 얻을 수 있다.

 

$\binom{n}{k}2^{1-\binom{k}{2}}$: monochromatic 하게 나올 수 있는 $K_k$ 의 갯수의 기댓값.

vertex를 하나씩 빼다보면 monochromatic clique들이 점점 사라질텐데, 가장 많이 뺀다면 저 만큼은 빼야 한다는 거고,

저거 뺸 거보다 큰 갯수만큼이 남아있다면, 그건 monochromatic clique 가 존재하는 그래프일 확률이 있으니까,

 

Definition

A set is dominating: $S \subseteq V(G)$ 바깥의 모든 vertex 가 $S$ 에 neighbor가 있다. 바깥으로 모든 edge를 가지는 vertex set

 

Theorem

For $k>1$, 모든 n-vertex graph, minimum degree가 $k$면

dominating set of size $\leq (\frac{1+ln(k+1)}{k+1})n$

임의의 $S$를 잡자. 어떤 vertex 가 $S$에 들어갈지 아닐지, 그 확률은 $p = \frac{\ln{(k+1)}{k+1}$.

그리고 S 밖에 있으면서, S에 친구(neighborhood)는 없는 $T$ 를 떠올려보자.

그러니까 $S+T$ 는 dominating set이다. 우리는 $[S \cup T]$ 의 expected number 를 다뤄볼거다.

 

S에 vertex가 있을 확률은 p, 그러니까 $\mathbb{E}[|S|] = np$.

RV $|T|$ 는 각 v가 T에 있을지 없을지, $n$에 대한 indicator rv. 예를들어 $v \in T$이면, $v$랑 $N(v)$ 들이 $S$에 못들어간단 얘기다. 이 확률은 최대 $(1-p)^{k+1}$ 야, 왜냐하면 $v$도 degree가 $k$보다는 크니까.

$(1-p)^{k+1} < e^{-p(k+1)}$ 이니까,

$\mathbb{E}[|S| + |T|] \leq np + ne^{-p(k+1)} = (\frac{1 + \ln{(k+1)}}{k+1})n$

그러니, $|S \cup T| \leq \mathbb{E}[|S| + |T|] \leq (\frac{1 + \ln{(k+1)}}{k+1})n$

 

Lemma <Markov's inequality>

X 가 discrete random variable 

$Pr[X \geq t] \leq \frac{\mathbb{E}[X]}{t}$. Thus, $\mathbb{E}[X] \rightarrow 0$ implies $Pr[X=0] \rightarrow 1$.

$\textit{Proof}$

$\mathbb{E}[X] = \sum_{k \leq 0}kPr[X=k] \geq t\sum_{k \geq t} Pr[X=k] = tPr[X \geq t]$

 

Theorem

$k \geq 3, g \geq 3$

girth 가 최소 $g$개 이상이고 chromatic number 가 최소 $k$ 인 그래프가 존재

$\textit{Proof}$

각 pair 마다 edge가 있을 확률이 $p$라고 하자. $p$가 크면 large independent set이 없다는 얘기고, $\chi(G) \geq n / \alpha(G)$ 로 $\chi(G)$도 크다는 사실을 알 수 있다. $p$가 작다면, short cycle 갯수의 기댓값이 매우 작다.  적절한 $p$를 골라야 chromatic number 는 크고, short cycle 은 적은 그래프가 나온다는 이야기. 일단 all short cycle 을 제거해나가는 방식으로 우리가 원하는 그래프를 찾아나가 보자.