rkm0959

Ramsey Number는 이산수학에서 중요하게 다뤄지는 주제 중 하나다. 

Ramsey Number $R(n, m)$는 정점이 $V$개인 완전그래프 $G$의 간선을 빨간색/파란색 중 하나로 색칠할 때, 빨간색 간선으로만 이루어진 완전그래프 $K_n$ 또는 파란색 간선으로만 이루어진 완전그래프 $K_m$이 존재하게 되는 $V$의 최솟값으로 정의된다. 

이를 확장해서, 그래프 $G_1, G_2$에 대해 $R(G_1, G_2)$를 정점이 $V$개인 완전그래프 $G$의 간선을 빨간색/파란색 중 하나로 색칠할 때, 빨간색 간선으로만 이루어진 $G_1$ 또는 파란색 간선으로만 이루어진 $G_2$가 존재하게 되는 $V$의 최솟값으로 정의하자.

본 포스팅에서는 1977년에 증명된 다음 정리를 증명한다. 

Theorem: (V. Chvatal) 

임의의 정점 $n$개를 가진 트리 $T_n$과 완전그래프 $K_m$에 대해서, $R(T_n, K_m) = (n-1)(m-1)+1$이 성립한다.

Theorem 증명

이제부터 빨간색 간선만 간선으로 본다. 즉, 이제부터 $G$는 빨간색 간선으로만 이루어진 그래프다. 

마찬가지로, $\overline{G}$는 파란색 간선으로만 이루어진 그래프다. 먼저 $R(T_n, K_m) \ge (n-1)(m-1)+1$을 보인다.

$K_{n-1}$을 $m-1$개 깔아놓은 것을 $G$라 하면, $G$는 $T_n$을 포함하지 않고 $\overline{G}$는 $K_m$을 포함하지 않는다. 

그러니 $R(T_n, K_m) > |V(G)| = (n-1)(m-1)$이 되고 $R(T_n, K_m) \ge (n-1)(m-1)+1$을 얻는다.

이제 $R(T_n, K_m) \le (n-1)(m-1)+1$이 성립함을 증명하자.

즉, $(n-1)(m-1)+1$개의 정점을 가진 그래프 $G$가 있다면, $G$가 $T_n$을 포함하거나 $\overline{G}$가 $K_m$을 포함함을 증명하자. 

$\overline{G}$가 $K_m$을 포함하지 않으면, $G$가 $T_n$을 포함함을 보이면 된다. 

보조정리 3개가 필요하다. 대부분 well-known인 것 같다. 

그래프 $H$의 채색수를 $\chi(H)$라 하고, 최대 독립집합의 크기를 $\alpha(H)$라 하자.

Lemma 1. $\chi(H) \cdot \alpha(H) \ge |V(H)|$가 성립한다. 

Proof of Lemma 1. $\chi(H)$개의 색깔로 그래프를 색칠하면, 각 색으로 칠해진 정점의 집합은 각각 독립집합이 된다. 

이제 비둘기집의 원리를 적용하면 증명이 간단하게 끝난다.

Lemma 2. $H$의 적당한 부분그래프 $H'$이 존재하여, $H'$의 각 정점의 차수가 $\chi(H)-1$ 이상이다. 

Proof of Lemma 2. 채색수를 유지하면서 정점을 삭제하는 것을 반복하자. 이 과정이 멈추면, 어떤 정점을 삭제해도 채색수가 감소하는 그래프를 얻게 된다. 이 그래프를 $H'$이라 하면, $H'$이 원하는 조건을 만족함을 보이자.

$H'$에 속하는 정점 $v$가 있어, $H'$에서 $v$의 차수 $d$가 $\chi(H)-2$ 이하라고 가정하자. 

한편, $H'$의 성질에 의해서 $H' - \{v\}$는 $\chi(H)-1$개의 색으로 색칠할 수 있다. 

이제 $d \le \chi(H)-2$가 성립하므로, $H' - \{v\}$를 $\chi(H)-1$개의 색으로 색칠한 뒤 $v$를 적당한 색으로 칠해서 $H'$ 전체를 $\chi(H)-1$개의 색으로 칠할 수 있게 된다. 그런데 $\chi(H) = \chi(H')$이 성립하므로, 이는 모순이다.

Lemma 3. $H$의 각 정점의 차수가 $n-1$ 이상이면, $H$는 임의의 정점 $n$개를 가진 트리 $T_n$을 부분그래프로 가진다.

Proof of Lemma 3. $n$에 대한 귀납법. $n \le 2$까지는 자명하다. 

이제 임의의 정점 $n$개를 가진 트리 $T_n$을 하나 준비하고, 트리의 리프 노드 $v$를 하나 잡자.

귀납 가정에 의해서, $H$는 $T_n - \{v\}$를 포함한다. 한편, $H$의 각 정점의 차수가 $n-1$ 이상이므로 적당하게 리프 노드 $v$를 $H$에서 찾은 $T_n - \{v\}$에 붙일 수 있다. 그러니 $H$는 $T_n$을 포함하고, 귀납법에 의해서 증명 끝.

이제 모든 준비가 끝났다. 본격적인 증명을 시작하자.

$\overline{G}$가 $K_m$을 포함하지 않는다는 것은 $\alpha(G) < m$이 성립한다는 것과 동치이다.

$|V(G)|=(n-1)(m-1)+1$이니, Lemma 1에 의해서 $\chi(G) \ge n$을 얻는다. 

Lemma 2에 의해서, $G$의 부분그래프 $H$가 존재하여 $H$의 각 정점의 차수가 $n-1$ 이상이다.

Lemma 3에 의해서, $H$는 $T_n$을 부분그래프로 가진다. 즉, $G$는 $T_n$을 부분그래프로 가진다.

여기서 $R(T_n, K_m) \le (n-1)(m-1)+1$을 얻고, 이제 $R(T_n, K_m) = (n-1)(m-1)+1$을 얻어 증명 끝.

문제

(Graham, Pollak 1972) Prove that the edge set of $K_n$ cannot be partitioned into the edge-disjoint union of less than $n-1$ complete bipartite subgraphs. Also, prove that this bound is tight.

스포 방지선

________________________________________________________________________________________________________________________

________________________________________________________________________________________________________________________

(증명) $K_n$의 각 정점을 $1, 2, \cdots , n$이라 하자. 우선 $n-1$개의 완전 이분 그래프로 $K_n$을 분할하는 것은 쉽다. 

귀류법으로, 완전 이분 그래프 $B_1 , B_2, \cdots B_m$이 $K_n$을 분할한다고 하자. (단, $m \le n-2$다.)

또한, 각 완전 이분 그래프 $B_k$ 안에서 두 disjoint independent set을 $L_k, R_k$라고 부르자.

즉, $B_k$의 간선은 $L_k$의 정점과 $R_k$의 정점 사이를 모두 연결한 것이다.

다음 조건을 만족하도록 $K_n$의 정점 $v$에 실수 $x_v$를 놓자. 

조건 1: 모든 $1 \le k \le m$에 대하여, $\displaystyle \sum_{v \in L_k} x_v = 0$이고, $\displaystyle \sum_{v=1}^n x_v = 0$ 

조건 2: $\displaystyle \sum_{v=1}^n x^2_v \neq 0$이다. 즉, 모든 $v$에 대해 $x_v$가 전부 $0$은 아니다.

이것이 가능함을 보이자. 기초적인 선형대수학을 알면 쉽게 보일 수 있다.

조건 1은 식의 개수가 $m+1$개인 하나의 Homogeneous한 연립방정식을 이룬다. 

변수의 개수가 $n$개이고 $m+1 < n$이므로, 이 연립방정식은 non-trivial 해를 가진다. 

그러므로 조건 1, 2를 만족하도록 정점 $v$에 실수 $x_v$를 놓을 수 있다. 

이제 $B_1 , B_2, \cdots B_m$이 $K_n$의 edge set을 완벽하게 분할하므로, 다음 식이 성립한다.

$$\sum_{1 \le i < j \le n} x_ix_j = \sum_{k=1}^m \left(\displaystyle \sum_{i \in L_k} x_i \right) \cdot  \left(\displaystyle \sum_{j \in R_k} x_j \right)$$