6.2 램지 정리(Ramzey's Theorem)

'비둘기집 원리'를 일반화시킨 '램지 정리'를 살펴본다. 이 정리의 이해가 어려울 수도 있다. 그런데, 한 번 시도해볼 만하다. 

---

자연수 $\boldsymbol{n}$, $\boldsymbol{t}$, $q_1,q_2,\cdots,q_n$ 가 주어졌다고 하자. 다음 조건을 만족시키는 최소 자연수 $R(q_1,q_2,\cdots,q_n; n, t)$가 존재한다. 

 

임의의 집합 $S$의 "크기가 $t$인 부분집합($t-$부분집합)들의 집합"을 $\chi(S,t)$라고 표기하자. $\chi(S,t)$의 $n$조각으로의 분할

   $\chi(S,t) = E_1 \cup E_2 \cup \cdots \cup E_n$,  $(\forall i, j, \ E_i \cap E_j =\varnothing)$

에 대하여 

  $|S| \geq {\color{green}{R(q_1,q_2,\cdots,q_n; n, t)}}$

라고 하면

   "$|T| \geq q_i$이며 $\chi(T,t) \subset E_i$

을 만족하는 $S$의 부분집합 ${\color{red}{T}}$ 와 ${\color{red}{i}} \in \left\{1,2,\cdots,n\right\}$가 존재한다.

---

🤪무슨 말일까?

   $\begin{align} &\boldsymbol{n} &\rightarrow {\rm (색깔의 수)}, \\ &\boldsymbol{t} &\rightarrow {\rm (전체 초변의 수)},  \\ &q_1,q_2,\cdots,q_n  &\rightarrow {\rm (주어진 색깔의 초변의 수)} \end{align}$

 

로 간주하고, '그래프 이론'으로 해석해 본다. 이것이 이해가 더 나을 것이다. 

---

3-초변 : 3개의 정점들로 구성된 집합

'$t-$초그래프(hypergraph)'는 정점과 '$t-$초변(hyperedge)'들로 구성된 조합론적 구조다. 여기서 '$t-$초변'은 $t$개의 정점들로 구성된 집합이다. 

→ $2-$초그래프는 그래프와 같은 개념이다. 통상적으로 '그래프'는 정점과 변으로 구성되는데 이 경우의 변은 두 정점을 잇는 선분이다. 따라서 변을 2개의 정점으로 구성된 집합으로 보면 '$2-$초변'이다. 

완전 3-초그래프의 임의의 초변 $\boldsymbol e$의 형태

임의의 정점의 집합 $S$에 대하여 '초변 집합'이 $\chi (S,t)$인 초그래프를 '완전 $t-$초그래프'라 하자. 

→ 완전 2-초그래프는 '완전그래프'이다. 여기서 완전그래프 $K_n$는 각각의 $n$개의 정점에 대하여 다른 모든 정점이 서로 연결된 단순 그래프이다. 

이때, $X(S,t)$의 $n$개의 집합

   $E_1, E_2, \cdots, E_n$

으로의 분할은 완전 $t-$초그래프의 초변들을 $n$개의 서로 다른 색깔로 색칠하는 것과 같다. 

→ $E_i$의  완전 $t-$초그래프의 초변들은 같은 색깔 $i$로 칠해진다. 

 

이 경우 다음 성질

   "$|T|\geq q_i$이며 $\chi (T,t)$는 $E_i$의 부분집합" 

을 만족하는 ${\color{red}{T}}(\subset S)$는 같은 색을 갖는 '클리크(clique)'이라고 한다.

---

따라서 램지이론에 의하면 

   $R(q_1, q_2, \cdot, q_n; n, t)$

개 이상의 정점을 가진 완전 $t-$초그래프의 초변들을 $n$개의 색깔로 색칠한다면,

   $1$번 색깔의 크기 $q_1$의 '클리크'을 가지거나,

      또는

   $2$번 색깔의 크기 $q_2$의 '클리크'을 가지거나,

   $\cdots$, 

      또는

   $n$번 색깔의 크기 $q_n$의 '클리크'을 갖는다. 

---

우리에게 통상적으로 익숙한 '완전 $2-$초변 그래프(=완전그래프)'로 생각해 보면, 위의 내용을 이해하기가 수월하다.

 

엄격한 증명에 대한 이해는 아직 우리들의 영역이 아니니 부담갖지 않는 것이 여러모로 좋다. 완벽을 추구하게 되면 더 앞으로 나아가는 것이 힘들고 어려울 수 있다. 이것을 어떻게 활용할 지에 대해 생각하는 것이 더 효과적이다. 그러다보면 원론적이고, 본질적인 것에 관심이 생기게 될지도 모를 일이다. 

 

 

램지 정리에 의해 존재하는 자연수 $R(q_1, q_2, \cdot, q_n; n, t)$를 '램 지수(6.3. 램지 수(Ramsey number))'라 하고 일반적으로 $n=t=2$일 경우

   $R(p,q; 2,2) = R(p,q)$

로 표기한다. 

 

$\chi(S,1)$는 S와 표준적으로 '일대일 대응'이므로 '완전 1-초그래프'는 집합과 동치인 개념이다. $t=1$일 경우, '램지 정리'는 '비둘기집 원리'와 같다.
     $R(q_1, q_2, \cdots, q_n; n, 1) = q_1+q_2+\cdots+q_n -n+1$