램지의 정리

램지 이론에서 램지의 정리(영어: Ramsey’s theorem)는 충분히 큰 완전 그래프의 변을 색칠할 경우, 동색의 클릭을 찾을 수 있다는 정리이다.

정의

집합 $S$의, 크기가 $m$인 부분 집합들의 집합을 $\textstyle {\binom {S}{m}}$이라고 표기하자.

임의의

• 양의 정수 $c\in \mathbb {Z} ^{+}$ ("색깔의 수")
• 양의 정수 $m\in \mathbb {Z} ^{+}$ ("초변의 크기")
• 양의 정수 $n_{1},\dots ,n_{c}\in \mathbb {Z} ^{+}$ ("주어진 색깔의 초변의 수")

가 주어졌다고 하자. 램지의 정리에 따르면 다음 조건을 만족시키는 양의 정수 $R(n_{1},\dots ,n_{m};c,m)$가 존재한다.

임의의 집합 $S$ 및 $\textstyle {\binom {S}{m}}$의 $c$개 조각으로의 분할 $\textstyle {\binom {S}{m}}=E_{1}\sqcup \cdots \sqcup E_{c}$에 대하여, 만약 $|S|\geq R(n_{1},\dots ,n_{c};c,m)$라면, 다음 조건을 만족시키는 부분 집합 $T\subseteq S$와 $i\in \{1,\dots ,c\}$가 존재한다.

$|T|\geq n_{i}$이며, $\textstyle {\binom {T}{m}}\subseteq E_{i}$이다.

이는 그래프 이론으로 해석할 수 있다. $m$-초그래프(영어: hypergraph)는 꼭짓점과 $m$-초변(영어: hyperedge)들로 구성된 조합론적 구조이며, 여기서 $m$-초변은 $m$개의 꼭짓점들로 구성된 집합이다. (즉, 2-초그래프는 그래프와 같은 개념이다.) 임의의 꼭짓점 집합 $S$에 대하여, 초변 집합이 $\textstyle {\binom {S}{m}}$인 초그래프를 완전 $m$-초그래프라고 하자. (즉, 완전 2-초그래프는 완전 그래프이다.) 이 경우, $\textstyle {\binom {S}{m}}$의 $c$개 조각으로의 분할은 완전 초그래프의 초변들을 $c$개의 색깔로 색칠하는 것과 같다. 이 경우, 위와 같은 성질을 갖는 $T$는 동색의 클릭이라고 한다.

따라서, 램지 정리에 따르면, $R(n_{1},\dots ,n_{c};c,m)$개 이상의 꼭짓점을 가진 완전 $m$-초그래프의 초변들을 $c$개의 색깔로 색칠한다면, 1번 색깔의, 크기 $n_{1}$의 클릭을 가지거나, 아니면 2번 색깔의, 크기 $n_{2}$의 클릭을 가지거나, …… 또는 $c$번 색깔의, 크기 $n_{c}$의 클릭을 갖는다.

램지 정리에 따라 존재하는 양의 정수 $R(n_{1},\dots ,n_{c};c,m)$을 램지 수(영어: Ramsey number)라고 한다. 일반적으로, $c=m=2$일 경우 $R(r,s;2,2)=R(r,s)$로 표기한다.

무한 램지 정리

위의 (유한) 램지 정리의 확장으로, 다음과 같은 무한 램지 정리(영어: infinite Ramsey theorem) 역시 성립한다.

임의의 $m,c\in \mathbb {Z} ^{+}$ 및 임의의 가산 무한 집합 $S$ 및 $\textstyle {\binom {S}{m}}$의 $c$개 조각으로의 분할 $\textstyle {\binom {S}{m}}=E_{1}\sqcup \cdots \sqcup E_{c}$에 대하여, $\textstyle {\binom {T}{m}}\subseteq E_{i}$가 성립하는 무한 부분 집합 $T\subseteq S$와 $i\in \{1,\dots ,c\}$가 존재한다.

즉, 이는

$\aleph _{0}=R(\aleph _{0},\aleph _{0},\dots ,\aleph _{0};m,c)$

로 생각할 수 있다.

자명한 경우

$\textstyle {\binom {S}{1}}$는 $S$와 표준적으로 일대일 대응하므로, 완전 1-초그래프는 집합과 동치인 개념이다. 이 경우, $m=1$일 경우 램지 정리는 비둘기집 원리와 같다. 즉, 램지 정리는 비둘기집 원리의 일반화로 생각할 수 있다. 이 경우 물론

$R(n_{1},\dots ,n_{c};c,1)=n_{1}+\cdots +n_{c}-c$

이다.

$c=1$일 경우, 램지 정리는 자명하게 성립하며, 이 경우 자명하게

$R(n;1,m)=n$

이다.

$m=c=2$일 경우 다음과 같은 램지 수들은 자명하다.

$R(1,n)=R(n,1)=1$

$R(2,n)=R(n,2)=n$

알려진 몇 가지 램지 수

대부분의 경우 램지 수의 정확한 값은 거의 알려져 있지 않고, 범위의 형태로만 확인되어 있다. 알려진 램지 수는 다음과 같다.

r,s	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	9	14	18	23	28	36	40 – 42
4	1	4	9	18	25	36 – 41	49 – 61	56 – 84	73 – 115	92 – 149
5	1	5	14	25	43 – 48	58 – 87	80 – 143	101 – 216	126 – 316	144 – 442
6	1	6	18	36 – 41	58 – 87	102 – 165	113 – 298	132 – 495	169 – 780	179 – 1171
7	1	7	23	49 – 61	80 – 143	113 – 298	205 – 540	217 – 1031	233 – 1713	289 – 2826
8	1	8	28	56 – 84	101 – 216	132 – 495	217 – 1031	282 – 1870	317 – 3583	331 – 6090
9	1	9	36	73 – 115	126 – 316	169 – 780	233 – 1713	317 – 3583	565 – 6588	581 – 12677
10	1	10	40 – 42	92 – 149	144 – 442	179 – 1171	289 – 2826	331 – 6090	581 – 12677	798 – 23556

$c\geq 3$일 경우, 알려진 유일한 (자명하지 않은) 램지 수는

$R(3,3,3;3,2)=17$

이다.

R(3,3)=6의 증명

크기가 5인 완전 그래프의 경우, 크기 3의 클릭이 존재하지 않도록 2개 색으로 색칠할 수 있다. 즉, $R(3,3)>5$이다.

6개의 꼭짓점을 가지는 완전 그래프의 각 변을 빨강과 파랑으로 칠한다. 한 꼭짓점 v를 보면, 그 꼭짓점에는 5개의 변이 연결되어 있다. 비둘기집 원리에 의해, 적어도 그 중 3개는 같은 색이다. 그 색을 파랑이라고 가정 하고, 그 3개의 변에 연결된 꼭짓점을 각각 r, s, t라고 하자.

만약 변 (r, s), 변 (t, r), 변 (s, t) 중 어느 하나라도 파랑이면, v와 함께 파란색 삼각형(3개의 꼭짓점을 가지는 완전 그래프)이 생긴다. 만약 어느 하나도 파란색이 아니면, (r, s), (t ,r), (s, t)는 모두 빨간색이므로 빨간색의 삼각형이 생긴다. 그러므로, 6개의 꼭짓점을 가지는 완전그래프 K₆의 변을 두 가지 색으로 칠하는 경우, 동일한 색의 K₃를 포함하게 된다. 즉, R(3,3) ≤ 6이다.

한편, K₅를 두가지 색으로 칠하는 방법 중에는 동일한 색의 삼각형을 만들지 않는 경우가 존재한다(오른쪽 그림). 그러므로, R(3,3) > 5이다. 결론적으로 R(3,3)=6

역사

프랭크 램지가 1930년에 1차 논리의 특정 부분 집합의 결정 문제를 증명하는 도중 보조정리로서 증명하였다. 이는 훗날 에르되시 팔 등에 의하여 발전된 램지 이론의 시초로 여겨진다.

외부 링크

• “Ramsey theorem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 

같이 보기

• 램지 이론