R(3,4)=9 의 증명

점 여섯 개를 찍어서 적당히 이으면 그 중에 세 개가 서로 전부 연결되어 있거나 (즉, 삼각형이 되거나) 또는 세 개가 전혀 연결되어 있지 않은 경우가 반드시 존재한다. 증명은 이렇게 한다. 한 점에 3개 이상이 점이 연결되어 있다면 그 3점 중에서 어느 두 점만 연결되어도 삼각형이 된다. 어느 두 점도 연결되어 있지 않다면 그 세 점이 서로 떨어진 세 점이 되는 것이다. 마찬가지로 어느 한 점에 3개 이상의 점이 연결되어 있지 않다고 해도 같은 방법으로 논증이 가능하다.

이런 질문도 할 수 있는데, m개의 점이 서로 전부 연결되거나 또는 n개의 점이 서로 전혀 연결이 없는 경우가 반드시 존재하는 m, n에 의존하는 최소의 점의 개수가 과연 존재할까? 그게 존재한다는 것을 Ramsey가 증명했다고 하는데 어케 했는지 본인도 잘 모른다. 아무튼 희안하게도 보통 문제를 제시한 사람의 이름이 붙는게 보통인데 이건 문제를 푼 사람의 이름이 붙어있다. 페르마의 마지막 정리, 푸앵카레 추측 뭐 그런것들 ㅎㅎㅎ

https://en.wikipedia.org/wiki/Ramsey_problem
http://mathworld.wolfram.com/RamseyNumber.html

아무튼 그래서 그 값을 보통 R(m,n)이라고 표기하는게 보통이다. 위 논증에 의하면 R(3,3) \le 6 인 것이다. 그런데 다섯개의 점을 이어서 어느 세 점도 전부 이어지거나 어느 세 점도 전부 이어지지 않게 만들 수 있다. (한 번 그려보라) 따라서 R(3,3) = 6 이 된다.

R(3,4)의 값이 9라는걸 보고 증명을 해 봤는데, 본인의 증명은 경우를 좀 많이 나눠서 꽤 복잡한 풀이가 되었다. 그래서 인터넷을 뒤져보니 역시 훨 간단하게 푼게 있었다. 그 방법으로 한 번 증명해 보겠다.

먼저 세 점이 모두 연결되어 있으면 조건 1을 만족한다고하고, 네 점이 모두 연결되어 있지 않으면 조건 2를 만족한다고 정의하자.
어떤 점 A에 네 점 이상이 연결되어 있다면, 그 네 점중 어느 두 점만 연결해도 조건 1을 만족한다. 그 네 점이 모두 떨어져 있다면 조건 2를 만족한다. 따라서 9개의 점 중에 어느 한 점이라도 4개 이상의 점과 이어지면 조건 1 또는 2를 만족하게 된다.
만약 어떤 점 A에 여섯 개의 점이 이어져 있지 않다면 위에서 본 바대로 R(3,3)=6 이므로 그 안에는 조건 1을 만족하거나 또는 세 점이 서로 연결되어 있지 않다. 세 점이 서로 연결되어 있지 않다면 A와 그 세 점은 조건 2를 만족한다. 따라서 어느 한 점이라도 여섯개의 점과 이어져 있지 않다면 (즉, 2개 이하의 점과 연결된다면) 조건 1 또는 2를 만족한다.
결국 남은 가능성은 모든 점이 3개의 점과 이어져 있는 경우인데, 이런 경우는 불가능하다. 이 경우 edge의 개수는 9×3/2개가 되어야 하는데 정수가 되지 않기 때문이다.
따라서 R(3,4) \le 9이다.

마지막으로 여덟개의 점으로 조건 1, 2를 모두 만족하지 않게 그려야 하는데, 다음과 같이 그리면 된다.

(어느 사이트에서 슬쩍 카피 ㅋㅋ)
그래서 R(3,4)=9 가 된다. ㅎㅎㅎ

R(4,6)의 값은 아직 미해결 문제이다. 예전에 컴퓨터로 이거 한번 찾아보려고 프로그램을 짜서 열라 돌렸는데 결국 실패-_- 그 때 시도한 방법은 컴퓨터로 무식하게 돌리면 너무 시간이 오래 걸리니 약간 judicious guessing을 하려고 했는데 별로 judicious하지 못했다-_-

R(3,k)의 asymptotic behavior가 알려져 있는데 적당한 상수 C_1, C_2 가 존재해서

\displaystyle \frac{C_1 k^2}{\log k} \le R(3,k) \le\frac{C_2 k^2}{\log k}

라는 것이 김정한 박사에 의해 증명되었다. 이것으로 1997년에 Fulkerson 상을 수상했다.

2 thoughts on “R(3,4)=9 의 증명

  1. Ramsey는 본래 경제학자였다죠… 27살에 죽어 단명한.

    Ramsey 정리는 Ramsey가 창안하긴 했지만 결국 Erdos(와 Szekeres)에 의해 다시 이재발견되어 빛을 보게 된 것 같습니다. 재미있는 것은 Erdos와 Szekeres는 그들이 독자적으로 이 정리를 증명하였는데 처음에는 Ramsey가 이 정리를 증명한지 몰랐다고 하더군요. ㅎㅎㅎ

    Erdos에 대한 영화의 일부인 다음 동영상도 재미있게 볼만합니다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중