램지의 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

충분히 큰 완전 그래프의 변(edge)을 색칠하게 되면, 동일한 색의 변으로만 구성된 완전 그래프가 포함되어 있다. 양의 정수 (r,s)에 대해, 정수 R(r,s)이 존재하는데, R(r,s) 이상의 꼭짓점을 가지는 완전 그래프의 변을 빨강파랑 두가지 색으로 칠하게 되면, 그 그래프는 r개 이상의 꼭짓점을 가지는 파랑 완전 그래프나 s개 이상의 꼭짓점을 가지는 빨강 완전 그래프, 둘 중의 어느 하나를 부분 그래프로 포함하게 된다. 이것을 램지의 정리라고 한다. 당연히 정수 R(r,s)은 rs에 의존한다. 세 가지 이상의 색이 칠해진 경우, 즉 R(r,s,t,...)도 연구되고 있다.

R(3,3)=6의 증명[편집]

A 2-coloring of K_5 with no monochromatic K_3

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

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

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

알려진 몇 가지 램지 수[편집]

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

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 – 49 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

이 표는 스테인슬러 래드지스조스키의 논문[1]에서 가져왔다.

일반화한 램지의 정리[편집]

램지의 정리는 비둘기집 원리에서 상자에 넣는 물건을 물건들의 부분집합으로 일반화한 형태이다. 전체 내용은 다음과 같다.

자연수 q_1, q_2, ... , q_n, tq_1 \ge t, q_2 \ge t, ... , q_n \ge t을 만족할 때, 다음 성질을 만족하고 q_1, q_2, ... , q_n, t에 의존하는 최소의 자연수 N(q_1, q_2, ... , q_n; t)가 존재한다.

m \ge N(q_1, q_2, ... , q_n; t)이고 Sm개의 물건으로 이루어진 집합일 때, S의 t-부분집합들을 n개의 상자에 넣으면 q_1개의 물건이 존재하여 그 중 모든 t-부분집합들이 첫 번째 상자에 있거나, q_2개의 물건이 존재하여 그 중 모든 t-부분집합들이 두 번째 상자에 있거나, ……, q_n개의 물건이 존재하여 그 중 모든 t-부분집합들이 n번째 상자에 있다.

t=1이고 q_1=q_2=...=q_n일 경우는 일반적으로 알려진 비둘기집 원리와 같으며, R(r,s)=N(r, s; 2)이다.