High Girth & High Chromatic with Probabilistic method

HGHC는 graph theory / combinatorics에서 오랫동안 제기되어 왔던 추측을 반증하는 lemma로, 확률론적 방법의 대표적인 예제이다.

확률론적 방법의 진수를 보여주는 lemma라고 생각하는데, 확률론적 방법 전체를 소개하기에는 너무 길고, 이 정리의 증명만 포스트에 싣기로 한다. 아마 wikipedia 수준의 사전 지식 이외에는 필요하지 않을 것이다.

Thanks to. claim

---

0. Introduction

임의의 자연수 \(t, \ u\)에 대해 \(g(G) > t\)와 \(\chi (G) > u\)를 동시에 만족하는 그래프 \(G\)가 존재한다.

여기서 그래프의 girth \(g(G)\)는 \(G\)에서 가장 작은 cycle의 크기를 의미하고, 

\(\chi (G)\)의 경우 graph coloring에 필요한 최소 색의 수이다.

즉 그래프를 몇 개의 집합으로 나누었을 때, 인접한 정점의 색이 다르도록 하기 위해 필요한 집합의 최소 개수가 \(\chi (G)\)가 된다.

직관적으로 보면, 사이클의 평균 크기를 나타내는 \(g(G)\)가 커질수록 \(\chi(G)\)가 작아져야 할 것 같다. 하지만 그 믿음을 HGHC가 산산조각내어 버렸다. '반증을 위한 증명'의 대표적인 사례라고 볼 수 있다.

---

1. Girth

확률변수 \(X\)를 크기가 \(t\)이하인 cycle의 개수, 

\(X_i\)를 크기가 \(i\)인 cycle의 개수로 생각하고,

임의의 edge를 연결해 줄 확률값을 \(p\)로 잡자.

이 때, 정점 \(n\)개의 그래프에서

$$ \begin{align*} \mathbb{E} [X_k] = \begin{pmatrix} n \\ k \end{pmatrix} p^{k} \cdot k! \end{align*} $$

가 성립하고, 또 \( \begin{pmatrix} n \\ k \end{pmatrix} \cdot k! < \frac{n^k}{2} \)이므로 \( \mathbb{E}[X_k] = \frac{1}{2} (np)^k \)이다.

이 때 확률 \(p\)를 \(n^{-1+\lambda}\)로 잡으면 \((\lambda \cdot t << 1 )\)

\( \sum_{k=3}^{t} E[X_{k}] < \sum_{k=3}^{t} \frac{1}{2} n^{-\lambda k} < \frac{n^{-\lambda t}}{2(1-n^{-\lambda})} < \frac{n}{4} \text{ for sufficiently small }\lambda. \)

이 때 Markov's inequality 에 의해, \(\text{Pr}(X > \frac{n}{2}) < \frac{\mathbb{E}[X]}{n/2} < \frac{1}{2}\) 가 성립한다.

---

2. Chromatic Number

그래프의 최대 독립 집합 의 크기를 \(\alpha (G)\)라고 하면, 하나의 색에 대해서 한 색으로 칠해진 정점들은 하나의 독립 집합이므로 그 크기는 \(\alpha (G)\) 이하이다. 때문에 다음이 성립한다.

$$\chi(G)\alpha(G) \ge n$$

이 \(\alpha (G)\)의 성질을 이용할 것인데, \(\alpha (G)\)가 어떤 수 \(a\)보다 크려면 \(a\)개의 정점을 골랐을 때 그 정점들로 구성된 부분그래프가 anti - complete graph. 즉 에지가 하나도 없는 그래프여야 하므로,

\(\text{Pr}(\alpha(G) \ge a) \le \begin{pmatrix} n \\ a \end{pmatrix} (1-p)^{\begin{pmatrix} a \\ 2 \end{pmatrix}} \le \begin{pmatrix} n \\ a \end{pmatrix}e^{-p\begin{pmatrix} a \\ 2 \end{pmatrix}} \le n^{a}e^{-pa(a-1)/2}\)가 성립하는데,

\(a\)를 \(\frac{3ln n}{p}\)로 잡으면 \(\text{Pr}(\alpha(G) \ge a) \le n^a e^{-pa(a-1)/2} \le n^a n^{-1.5(a-1)} \rightarrow 0\)이 성립한다. 따라서 충분히 큰 \(n\) 즉 충분히 큰 \(a\)에 대해 \(\chi(G) \ge \frac{n}{\alpha(G)} \ge \frac{n}{a} \ge \frac{np}{3ln n} = \frac{n^{\lambda}}{3 ln n} \rightarrow \infty\) 이다. (1에서 \(p = n^{-1 + \lambda}\)로 정의했다)

---

3. Conclusion

충분히 큰 \(n\)에 대해서, \(\text{Pr}(X > \frac{n}{2} \vee \alpha(G) \ge a) < 1\)이고, 따라서 \(X \le {n}{2} \wedge \alpha(G) \ge a\)를 만족하는 그래프 \(G\)가 반드시 존재한다.

이 때, 

- 크기가 \(t\)이하인 cycle에서 아무 생각 없이 정점을 골라서 제거해 주자. 

- 그럼 \(\alpha (G)\)의 상한은 변하지 않지만 

- \(t\)보다 작은 cycle은 남지 않게 되고

- \(t\)보다 작은 크기의 cycle이 없는 정점이 최소 \(\frac{n}{2}\)개 이상 남아 있으며

- 얘네를 이어서 \(\frac{n}{2}\)보다 큰 크기의 cycle을 만들 수 있다.

- \(\chi(G) \ge \frac{V(G)}{\alpha (G)} \ge \frac{n/2}{\alpha (G)} \ge \frac{n^\lambda}{6 \ln n} \rightarrow \infty\)이므로 주어진 명제를 증명할 수 있다. \(\blacksquare\)