Ramsey Number of a Tree and a Complete Graph

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\)을 얻어 증명 끝.