램지 이론(Ramsey theorem)이란 조합론, 그래프 이론의 한 분야로써 구조의 크기에 영향을 받는 수학적 구조의 대표적인 예시이다.

동시에 이는 단순해 보이는 구조가 실제로는 얼마나 ㅈ같이 복잡할 수 있는지를 알려주기도 한다.

( 본 글은 Arthur Engel 교수님의 PSS를 사실상 갖다 놓은거다. 읽기 뭐하면 책 찾아읽어라. )

다음 문제는 매우 유명한 문제다. (1953 putnam에서 제시되었다고 한다.)

" 6명의 사람이 모였다. 이 중에는 서로 알거나 서로 전혀 모르는 3명이 반드시 있다. "

이 문제를 풀기 전에, 그래프 이론에서 사용하는 완전 그래프 G_p 라는 것에 대해 알고 넘어갈 필요가 있다.

완전 그래프 G_p 라는 것은, 임의의 두 점 사이를 선분으로 모두 이은 점이 p개인 그래프를 의미한다. 자세한 건 이산수학 책을 참고해라

그러면 6명이 사람이 서로 알거나 모르는 것 따위를 어떻게 표현할까?

여기서 우리는 G_6을 생각하고 서로 알면 (선분에) 빨간색, 서로 모르면 파란색을 칠하는 걸 생각할 수 있는데, 서로 알거나 서로 모르는 3명이 있다는 말은

이 그래프 안에 (어떤 색깔이든) 삼각형이 존재할 수 밖에 없다는 말이다.

여기서 중요한 건, 5명일 때는 서로 알거나 서로 모르는 3명이 있든 말든 모르겠지만, 6명일 때부터는 이런 사람이 반드시 생기는 것,

즉 크기가 수학적 구조에 영향을 주는 예시라고 할 수 있겠다

이제 6명이 있으니 두 색깔로 색칠한 완전그래프 G_6을 생각하고 위 문제를 풀어보자.

1. 적당히 한 정점을 택하고 이를 P라고 둔다. 당연하지만 완전그래프이므로 이 정점에는 5개의 선분이 연결되어 있어야 한다

2. 당연하지만 이 선분들 5개 중에서 최소한 3개는 동일한 색깔이어야 한다. (비둘기집의 원리)

3. 이 동일한 색깔을 빨간색이라 치고, 이제 이 3개의 선분이 각 점 A, B, C에 연결되어 있다고 가정하자

4. 그러면 다음과 같은 사면체(?) 를 생각할 수 있다.

5. AB나 BC, 혹은 CA는 절대 빨간색이 되어서는 안 된다. (빨간색이면 삼각형이 생긴다)

그러면 AB, BC, CA는 전부 같은 색이 되고, 이는 삼각형 ABC를 만든다

따라서 서로 모르는 3명이나 서로 아는 3명이 반드시 존재하게 된다. (6명이 모이면)

근데 이러한 논의가 색을 3개 이상으로 칠하거나 하는 것에 대해서도 유효할까? 수학자들은 줄줄이 모여가서 골싸매고 이 문제를 일반화했고,

그래서 나온 것이 바로 램지 정리 (Ramsey's theorem)이다.

이제 G_p의 모든 모서리들을 n개의 색깔로 색칠한 것을 'n색 G_p' 라고 하고, 이 'n색 G_p' 가 세 변이 같은 색인 삼각형을 하나라도 포함하면 G_p는 단색이라고 하기로 한다.

이제 다음 문제를 풀어보자.

" 17명의 과학자들이 모두 서로 2명씩 공동연구를 한다. 모든 연구의 주제는 3가지이고 임의의 두 명은 한 가지 연구만을 한다. 서로서로 동일한 공동연구를 하는 과학자가 적어도 3명 있음을 보여라. "

당연하지만 이거는 G_17을 느집 삼색볼펜으로 그리면 어떤 색깔만으로 변이 이루어진 삼각형이 있겠느냐? 라는 거고,

(아까 했듯이) 한 점을 생각하면 연결된 16개의 선분 중 적어도 6개는 같은 색깔이 된다는 걸 알 수 있다. 이걸 빨간색이라 하자

이 6개의 점들도 서로 연결되어 있을거고, (사실 이건 G_6이다.) 이 선분들 중에 하나라도 빨간색이 있으면 삼각형이 생긴다.

따라서 이 6개의 점들은 빨간색을 제외한 두 색이어야 하고... 근데 위에서 6명이 모이고 이걸 두색으로 색칠하면 적어도 삼각형이 하나는 있다 했으니 문제가 증명되었다.

이제 램지 정리의 일반적인 형태를 주자.

" 두 개 이상의 정수 q_1, ... , q_n 에 대해서, G_p가 한 색으로 이루어진 G_q_i ( i = 1, .. , n) 를 적어도 하나 포함하는 p >= R(q_1, ... , q_n) 인 최소의 수 R이 존재한다"

물론 R은 자연수다.

이러한 수 R을 램지 수(Ramsey number) 이라고 한다. 위의 두 예제는 R(3,3) = 6, R(3,3,3) = 17 로 표현할 수 있겠다.

이러한 램지 수는 진짜 존나게 찾기 힘들어서 지금도 알려진 수가 몇개 없다.

여기에 대해서 폴 에어디쉬(Paul Erdos)가 남긴 농담(?)이 하나 있는데, 이걸 소개하면서 마친다.

" 외계인들이 지구를 침략해서 R(5,5)를 1년 내에 계산해내지 않으면 지구를 없애버리겠다고 협박한다 치자. 그러면 우리는 세계에서 제일 머리좋은 사람들과 최고의 컴퓨터를 동원해서 1년 내로 그 값을 찾아낼 수 있을 것이다. 근데 R(6,6)을 계산해라 한다면 우리는 선제타격을 해야 한다. "

* PSS에서는 R(3,3, .. ,3) <= [en!] + 1 (3이 n개) 의 증명을 주고 있다. 읽어볼 만 하니 읽어봐라.