램지의 정리

램지 이론에서 **램지의 정리**(Ramsey’s theorem)는 충분히 큰 완전 그래프의 변을 색칠할 경우, 동색의 클릭을 찾을 수 있다는 정리이다.
# 정의
집합 S의, 크기가 m인 부분 집합들의 집합을 \textstyle\binom Sm이라고 표기하자. 임의의 * 양의 정수 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 Sm의 c개 조각으로의 분할 \textstyle\binom Sm=E_1\sqcup\cdots\sqcup E_c에 대하여, 만약 |S|\ge R(n_1,\dots,n_c;c,m)라면, 다음 조건을 만족시키는 부분 집합 T\subseteq S와 i\in\\{1,\dots,c\\}가 존재한다. ::|T|\ge n_i이며, \textstyle\binom Tm\subseteq E_i이다. 이는 그래프 이론으로 해석할 수 있다. m-**초그래프**(hypergraph)는 꼭짓점과 m-**초변**(hyperedge)들로 구성된 조합론적 구조이며, 여기서 m-초변은 m개의 꼭짓점들로 구성된 집합이다. (즉, 2-초그래프는 그래프와 같은 개념이다.) 임의의 꼭짓점 집합 S에 대하여, 초변 집합이 \textstyle\binom Sm인 초그래프를 **완전 m-초그래프**라고 하자. (즉, 완전 2-초그래프는 완전 그래프이다.) 이 경우, \textstyle\binom Sm의 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 Sm의 c개 조각으로의 분할 \textstyle\binom Sm=E_1\sqcup\cdots\sqcup E_c에 대하여, \textstyle\binom Tm\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 S1는 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
# 알려진 몇 가지 램지 수
대부분의 경우 램지 수의 정확한 값은 거의 알려져 있지 않고, 범위의 형태로만 확인되어 있다. 알려진 램지 수는 다음과 같다.언어=en {| class="wikitable" |- ! 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\ge3일 경우, 알려진 유일한 (자명하지 않은) 램지 수는 :R(3,3,3;3,2)=17 이다. ===*R*(3,3)=6의 증명=== 크기가 5인 클릭이 존재하지 않도록 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*6의 변을 두 가지 색으로 칠하는 경우, 동일한 색의 *K*3를 포함하게 된다. 즉, *R*(3,3) ≤ 6이다. 한편, *K*5를 두가지 색으로 칠하는 방법 중에는 동일한 색의 삼각형을 만들지 않는 경우가 존재한다(오른쪽 그림). 그러므로, *R*(3,3) > 5이다. 결론적으로 *R*(3,3)=6
# 역사
프랭크 램지가 1930년에 1차 논리의 특정 부분 집합의 결정 문제를 증명하는 도중 보조정리로서 증명하였다.언어=en 이는 훗날 에르되시 팔 등에 의하여 발전된 램지 이론의 시초로 여겨진다.