램지의 정리

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

램지 이론에서, 램지의 정리(영어: 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 Smc개 조각으로의 분할 \textstyle\binom Sm=E_1\sqcup\cdots\sqcup E_c에 대하여, 만약 |S|\ge R(n_1,\dots,n_c;c,m)라면, 다음 조건을 만족시키는 부분 집합 T\subseteq Si\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 Smc개 조각으로의 분할은 완전 초그래프의 초변들을 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 Smc개 조각으로의 분할 \textstyle\binom Sm=E_1\sqcup\cdots\sqcup E_c에 대하여, \textstyle\binom Tm\subseteq E_i가 성립하는 무한 부분 집합 T\subseteq Si\in\{1,\dots,c\}가 존재한다.

즉, 이는

\aleph_0=R(\aleph_0,\aleph_0,\dots,\aleph_0;m,c)

로 생각할 수 있다.

자명한 경우[편집]

\textstyle\binom S1S와 표준적으로 일대일 대응하므로, 완전 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

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

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

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

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

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), 변 (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 이다.

역사[편집]

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

참고 문헌[편집]

  1. Radziszowski, Stanisław P. (2014년 1월 12일). “Small Ramsey numbers”. 《The Electronic Journal of Combinatorics》 (영어) DS1: 14. 
  2. Ramsey, F. P. (1930). “On a problem of formal logic”. 《Proceedings of the London Mathematical Society》 (영어) 30: 264–286. doi:10.1112/plms/s2-30.1.264. 

바깥 고리[편집]

같이 보기[편집]