램지의 정리

위키백과 ― 우리 모두의 백과사전.

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

[편집] 예제: R(3,3)=6

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

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

한편, K₅를 두가지 색으로 칠하는 방법 중에는 동일한 색의 삼각형을 만들지 않는 경우가 존재한다(오른쪽 그림). 그러므로, 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–43
4	1	4	9	18	25	35–41	49–61	56–84	73–115	92–149
5	1	5	14	25	43–49	58–87	80–143	101–216	125–316	143–442
6	1	6	18	35–41	58–87	102–165	113–298	127–495	169–780	179–1171
7	1	7	23	49–61	80–143	113–298	205–540	216–1031	233–1713	289–2826
8	1	8	28	56–84	101–216	127–495	216–1031	282–1870	317–3583	≤ 6090
9	1	9	36	73–115	125–316	169–780	233–1713	317–3583	565–6588	580–12677
10	1	10	40–43	92–149	143–442	179–1171	289–2826	≤ 6090	580–12677	798–23556

이 표는 Stanisław Radziszowski의 논문[1]에서 가져왔다.