램지의 정리 편집하기

'''Ramsey's theorem'''

== 개요 ==

[[파일:five vertices graph.svg|200픽셀|썸네일|오른쪽|크기가 5일 때, 완전그래프는 변의 색이 모두 같은 크기가 3인 완전그래프를 포함하지 않는다.]]
자연수 ''r'', ''s''가 주어졌다고 하자. 어떤 충분히 큰 [[완전그래프]]의 변을 빨간색과 파란색으로 색칠한다고 할 때, 꼭짓점의 갯수가 ''r''이고 변의 색깔이 모두 빨간색이거나, 꼭짓점의 갯수가 ''s''이고 변의 색깔이 모두 파란색인 완전그래프를 포함한다. 이 때, 이 조건을 만족하는 최소의 꼭짓점의 개수를 <math>R(r,s)</math>로 표시한다.

잘 알려진 예는 <math>R(3,3) = 6</math>. 실생활에 적용하면, 6명의 사람이 있을 때, 서로 아는 3명이나 서로 모르는 3명이 존재한다. 크기가 5일 때에는 변의 색이 모두 같고 크기가 3인 완전그래프를 포함하지 않는다. 다음에 나올 증명에 의해<math>R(3,3) \leq 6</math>을 알 수 있어, <math>R(3,3) = 6</math>임을 알 수 있다.

== 증명 ==
귀납법을 사용한다. 대신에 두 변수에 대해 사용할 것이다.
* <math>R(r,2) = r, R(2,s)=s</math>
** 꼭짓점이 2개이면, 변은 1개다. 즉, 하나라도 다른 색이 있으면 꼭짓점의 개수가 2인 완전그래프를 포함하게 된다. 그것이 아니라면 모든 변의 색이 같아진다.
* 이제, <math>R(r-1,s), R(r,s-1)</math>이 존재한다고 가정하자.
** 한 꼭짓점을 고른다. 그리고 고른 꼭짓점과 연결된 변이 빨간색인 집합 ''A''와 파란색인 집합 ''B''으로 나눌 수 있다.
**# 만약 집합 ''A''의 원소의 개수가 <math>R(r-1,s)</math>이라면
**#* 변이 모두 빨간색이고 크기가 ''r-1''인 완전그래프가 있다면, 처음 고른 꼭짓점을 추가해 크기가 ''r''인 완전그래프를 얻을 수 있다.
**#* 변이 모두 파란색이고 크기가 ''s''인 완전그래프가 있다면 이걸로 끝.
**# 만약 집합 ''B''의 원소의 개수가 <math>R(r,s-1)</math>이라면
**#* 변이 모두 빨간색이고 크기가 ''r''인 완전그래프가 있다면 끝.
**#* 변이 모두 파란색이고 크기가 ''s-1''인 완전그래프가 있다면, 처음 고른 꼭짓점을 추가해 크기가 ''s''인 완전그래프를 얻을 수 있다.
** 그러면 이제 두 개로 나눴을 때 저 두 조건중 하나를 만족하려면 최소한 꼭짓점의 개수가 고를 꼭짓점 포함해서 <math>R(r-1,s) + R(r,s-1)</math>여야 한다. 이건 [[비둘기집의 원리]]에 의해 유도할 수 있다.
** <math>R(r-1,s) + R(r,s-1)</math>개의 꼭짓점이 있으면 ''r'', ''s''에 대해 램지의 정리를 만족하도록 할 수 있다. 상계값을 찾은 것이다. 그러므로 <math>R(r,s) \leq R(r-1,s) + R(r,s-1)</math>이다. 정확한 값은 알 수 없지만 존재한다는 것은 알 수 있다.

== 일반화 ==
꼭 색을 두 가지만 칠하라는 법은 없다. 여러 가지 색에 대해서도 똑같은 논리를 전개할 수 있다. 표현은 <math>R(r,s,t,...)</math>로 표시한다.

{{주석}}
[[분류:조합론]]
[[분류:수학 정리]]