램지 수(Ramsey number)
특히, $R(p,q)$인 '램지 수'에 대해 관심이 많다. 이 경우, 유한개의 점이 있고 임의의 두 점을 한 개의 선분으로 연결한 것을 '클리크'로 생각하면 된다. $k-$클리크라 하면 정확히 $k$개의 점을 갖는 클리크를 뜻한다.
따라서 $R(p,q)$의 값은 빨간색 $p-$클리크 또는 파란색 $q-$클리크가 존재하도록 하는 가장 작은 자연수 $m-$클리크를 의미한다. 즉, $m-$클리크의 각 선분들을 $2$개의 색, 빨강과 파랑으로 무작위로 칠했을때 빨간색 $p-$클리크 또는 파란색 $q-$클리크를 포함한다는 것이다.
예를 들어, $R(3,3)=6$이다.
$6-$클리크는 빨강과 파랑으로 무작위로 칠했을때 빨간색의 $3-$클리크 또는 파란색 $3-$클리크를 반드시 포함한다는 것을 의미한다. $R(3,3) \leq 5$에서는 다음과 같이 성립하지 않는 예($5-$클리크)가 있다.
$6-$클리크인 경우에 성립함을 제6장 1절-'예제2(6.1 비둘기집 원리)'에서 이미 보였다. 따라서
$5 < R(3,3) \leq 6$
이므로 $R(3,3)=6$임을 알 수 있다.
대칭성에 의하여 $R(p,q) = R(q,p)$임이 분명하다.
$R(2,q)$의 값을 생각해 보자.
$(q-1)-$클리크 모든 선분을 파란색으로 칠하면 빨간색 $2-$클리크 또는 파란색 $q-$클리크는 존재하지 않는다. 따라서
$R(2,q) > (q-1)$
이다. $q-$클리크를 생각하자. 어느 한 선분이 빨간색이면 이것은 빨간색 $2-$클리크를 의미한다. 그렇지 않으면 파란색 $q-$클리크가 발생한다. 따라서
$R(2,q) ≤ q$
이다. 이것으로부터 $R(2,q)=q$를 얻는다.
$R(1,q)$의 값은 얼마일까?
$1-$클리크는 정점 $1$개를 의미한다.
$R(1,q)>1$이면 $2-$클리크 이상이 발생하므로
$R(1,q) ≤ 1$
이어야 한다. 따라서 $R(1,q)= 1$이다.
'램지 수'에 대한 연구만으로도 존재감을 한껏 내뿜는 수학자들이 있다. 아직도 미지의 영역이다. 이 글을 읽는 어린 독자는 그 미지의 세계의 탐험을 꿈꿔보기 바란다. '램지 수'에 관한 다른 궁금한 내용들은 인터넷 검색을 통해서도 쉽게 접할 수 있을 것이다.
[덧붙이는 말]
R(3,3,3; 3, 2) = 17로 잘 알려져 있다. 16-클리크인 경우에 빨간색 3-클리크 또는 파란색 3-클리크 또는 초록색 3-클리크가 존재하지 않는 경우의 2가지 예이다.
'Counting의 기술' 카테고리의 다른 글
| 6.2 램지 정리(Ramzey's Theorem) (0) | 2022.09.18 |
|---|---|
| 6.1 비둘기집 원리 (0) | 2022.09.18 |
| 5.2 집합의 분할 (0) | 2022.09.18 |
| 5.1 자연수의 분할 (0) | 2022.09.18 |
| 4.3 지수 생성함수 (0) | 2022.09.17 |
댓글