램지의 정리 문서 원본 보기

{{위키데이터 속성 추적}}
[[램지 이론]]에서 '''램지의 정리'''({{llang|en|Ramsey’s theorem}})는 충분히 큰 [[완전 그래프]]의 변을 [[그래프 색칠|색칠]]할 경우, 동색의 [[클릭 (그래프 이론)|클릭]]을 찾을 수 있다는 정리이다.

== 정의 ==
집합 <math>S</math>의, 크기가 <math>m</math>인 [[부분 집합]]들의 집합을 <math>\textstyle\binom Sm</math>이라고 표기하자.

임의의
* 양의 정수 <math>c\in\mathbb Z^+</math> ("색깔의 수")
* 양의 정수 <math>m\in\mathbb Z^+</math> ("초변의 크기")
* 양의 정수 <math>n_1,\dots,n_c\in\mathbb Z^+</math> ("주어진 색깔의 초변의 수")
가 주어졌다고 하자. '''램지의 정리'''에 따르면 다음 조건을 만족시키는 양의 정수 <math>R(n_1,\dots,n_m;c,m)</math>가 존재한다.
:임의의 [[집합]] <math>S</math> 및 <math>\textstyle\binom Sm</math>의 <math>c</math>개 조각으로의 [[집합의 분할|분할]] <math>\textstyle\binom Sm=E_1\sqcup\cdots\sqcup E_c</math>에 대하여, 만약 <math>|S|\ge R(n_1,\dots,n_c;c,m)</math>라면, 다음 조건을 만족시키는 부분 집합 <math>T\subseteq S</math>와 <math>i\in\{1,\dots,c\}</math>가 존재한다.
::<math>|T|\ge n_i</math>이며, <math>\textstyle\binom Tm\subseteq E_i</math>이다.

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

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

램지 정리에 따라 존재하는 양의 정수 <math>R(n_1,\dots,n_c;c,m)</math>을 '''램지 수'''({{llang|en|Ramsey number}})라고 한다. 일반적으로, <math>c=m=2</math>일 경우 <math>R(r,s;2,2)=R(r,s)</math>로 표기한다.

=== 무한 램지 정리 ===
위의 (유한) 램지 정리의 확장으로, 다음과 같은 '''무한 램지 정리'''({{llang|en|infinite Ramsey theorem}}) 역시 성립한다.
:임의의 <math>m,c\in\mathbb Z^+</math> 및 임의의 [[가산 무한 집합]] <math>S</math> 및 <math>\textstyle\binom Sm</math>의 <math>c</math>개 조각으로의 [[집합의 분할|분할]] <math>\textstyle\binom Sm=E_1\sqcup\cdots\sqcup E_c</math>에 대하여, <math>\textstyle\binom Tm\subseteq E_i</math>가 성립하는 무한 부분 집합 <math>T\subseteq S</math>와 <math>i\in\{1,\dots,c\}</math>가 존재한다.
즉, 이는
:<math>\aleph_0=R(\aleph_0,\aleph_0,\dots,\aleph_0;m,c)</math>
로 생각할 수  있다.

=== 자명한 경우 ===
<math>\textstyle\binom S1</math>는 <math>S</math>와 표준적으로 [[일대일 대응]]하므로, 완전 1-초그래프는 [[집합]]과 동치인 개념이다. 이 경우, <math>m=1</math>일 경우 램지 정리는 [[비둘기집 원리]]와 같다. 즉, 램지 정리는 비둘기집 원리의 일반화로 생각할 수 있다. 이 경우 물론
:<math>R(n_1,\dots,n_c;c,1)=n_1+\cdots+n_c-c</math>
이다.

<math>c=1</math>일 경우, 램지 정리는 자명하게 성립하며, 이 경우 자명하게
:<math>R(n;1,m)=n</math>
이다.

<math>m=c=2</math>일 경우 다음과 같은 램지 수들은 자명하다.
:<math>R(1,n)=R(n,1)=1</math>
:<math>R(2,n)=R(n,2)=n</math>

== 알려진 몇 가지 램지 수 ==
대부분의 경우 램지 수의 정확한 값은 거의 알려져 있지 않고, 범위의 형태로만 확인되어 있다. 알려진 램지 수는 다음과 같다.<ref>{{저널 인용|url=http://www.combinatorics.org/ojs/index.php/eljc/article/download/DS1/pdf|제목=Small Ramsey numbers|저널=The Electronic Journal of Combinatorics|날짜=2014-01-12|이름=Stanisław P. |성=Radziszowski|권=DS1|쪽=14|언어=en}}</ref>

{| class="wikitable" style="text-align:center;"
! ''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
|}

<math>c\ge3</math>일 경우, 알려진 유일한 (자명하지 않은) 램지 수는
:<math>R(3,3,3;3,2)=17</math>
이다.

===''R''(3,3)=6의 증명===
[[파일:RamseyTheory_K5_no_mono_K3.PNG|섬네일|right|크기가 5인 [[완전 그래프]]의 경우, 크기 3의 [[클릭 (그래프 이론)|클릭]]이 존재하지 않도록 2개 색으로 색칠할 수 있다. 즉, <math>R(3,3)>5</math>이다.]]
6개의 꼭짓점을 가지는 완전 그래프의 각 변을 빨강과 파랑으로 칠한다. 한 꼭짓점 ''v''를 보면, 그 꼭짓점에는 5개의 변이 연결되어 있다. [[비둘기집 원리]]에 의해, 적어도 그 중 3개는 같은 색이다. 그 색을 파랑이라고 가정 하고, 그 3개의 변에 연결된 꼭짓점을 각각 ''r'', ''s'', ''t''라고 하자.

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

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

== 역사 ==
[[프랭크 램지]]가 1930년에 [[1차 논리]]의 특정 부분 집합의 결정 문제를 증명하는 도중 보조정리로서 증명하였다.<ref>{{저널 인용
 | doi =10.1112/plms/s2-30.1.264
 | last = Ramsey | first = F. P. | author-link = 프랭크 램지
 | journal = Proceedings of the London Mathematical Society
 | pages = 264–286
 | title = On a problem of formal logic
 | volume = 30
 | year = 1930 | 언어=en}}</ref> 이는 훗날 [[에르되시 팔]] 등에 의하여 발전된 [[램지 이론]]의 시초로 여겨진다.

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Ramsey theorem}}

== 같이 보기 ==
* [[램지 이론]]

[[분류:그래프 이론 정리]]
[[분류:램지 이론]]