램지 이론(Ramsey theory)

여섯 사람이 모이면, 그중에는 서로 모두 아는 세 사람이 있거나 서로 모두 모르는 세 사람이 반드시 있습니다. 사람을 점으로, 두 사람 사이를 선으로 긋고, 아는 사이면 빨강, 모르는 사이면 파랑으로 칠해 봅시다. 여섯 점을 모두 이은 그래프(완전 그래프⁠(complete graph)⁠ $K_6$)의 변 15개를 어떻게 칠하든 세 변이 모두 같은 색인 삼각형이 생깁니다.

. 꼭짓점⁠(vertex)⁠ 두 개를 차례로 누르면 그 사이 변의 색이 바뀝니다. 무작위로 칠하기 오각형 칠하기

다섯 명이면 피할 수 있습니다. '오각형 칠하기'처럼 오각형의 둘레를 빨강, 안쪽 별 모양을 파랑으로 칠하면 한 색 삼각형이 없습니다. 여섯 명에서 피할 수 없는 까닭은 비둘기집 원리⁠(pigeonhole principle)⁠입니다. 한 사람 A에게서 나가는 변은 5개인데 색은 둘뿐이므로, 같은 색 변이 적어도 3개 있습니다. 그것이 빨강이고 끝이 B, C, D라고 합시다. B, C, D 사이에 빨강 변이 하나라도 있으면 A와 함께 빨강 삼각형이 되고, 하나도 없으면 B, C, D가 파랑 삼각형입니다. 더 따져 보면 여섯 명일 때 한 색 삼각형은 언제나 적어도 두 개입니다.

램지 수⁠(Ramsey number)⁠. 어떻게 칠해도 빨강 $K_s$나 파랑 $K_t$가 생기게 하는 가장 작은 사람 수를 램지 수 $R(s, t)$라고 합니다. 방금 본 것이 $R(3,3) = 6$입니다. 1930년 영국의 수학자이자 철학자 프랭크 램지는 논리학 논문 속에서 이런 수가 언제나 유한하다는 것을 증명했습니다. 같은 논법을 되풀이하면 위의 부등식 $R(s,t) \le R(s-1,t) + R(s,t-1)$이 나오고, 거기서 $R(s,t) \le \binom{s+t-2}{s-1}$(이항계수⁠, binomial coefficient⁠)가 나옵니다.

정확한 값은 놀랄 만큼 알기 어렵습니다. $R(4,4) = 18$이지만, $R(5,5)$는 2020년대 기준으로 43 이상 46 이하라는 것만 알려져 있습니다. 43명이면 변이 903개라 칠하기가 $2^{903}$가지나 되어, 하나하나 따져 보는 방법은 가망이 없습니다. 43 이상이라는 것은 한 색 $K_5$가 없는 42명의 칠하기를 실제로 찾아 보인 결과입니다. k가 클 때 $R(k,k)$의 아래쪽 한계를 얻는 가장 유명한 방법은 무작위로 칠해 보는 확률적 방법⁠(probabilistic method)⁠입니다.

완전한 무질서는 없다. 램지 이론의 정리들은 모두 같은 모양입니다. 구조가 충분히 크면, 어떻게 나누거나 칠하든 한 조각 안에 질서 있는 부분이 생깁니다. 자연수⁠(natural number)⁠를 몇 가지 색으로 칠하면 한 색 등차수열⁠(arithmetic progression)⁠이 생기고(반 데르 바르던 정리⁠(van der Waerden's theorem)⁠), 평면에 어느 세 점도 한 직선 위에 있지 않게 찍은 다섯 점 가운데 넷은 언제나 볼록사각형(안으로 오목하게 들어간 꼭짓점이 없는 사각형)을 이룹니다. 또 서로 다른 수 $n^2+1$개를 늘어놓으면, 그중 몇 개를 순서를 지키며 골라 커지기만 하는 길이 n+1인 수열이나 작아지기만 하는 길이 n+1인 수열을 반드시 만들 수 있습니다. 예를 들어 2, 5, 1, 4, 3(n = 2, 수 5개)에서는 5, 4, 3이 작아지기만 합니다. 다섯 점 사실은 헝가리의 에스테르 클라인이 먼저 알아냈고, 1935년 에르되시와 죄르지 세케레시가 이를 더 많은 점으로 넓힌 논문에서 수열에 관한 사실도 함께 증명했습니다.

밤하늘의 별자리나 주가 그래프에서 '의미 있는 모양'을 찾을 때도 비슷한 조심이 필요합니다. 점이 충분히 많으면 어떤 모양은 배치와 상관없이 생기므로, 그 모양을 찾았다는 것만으로는 무언가 특별하다는 증거가 되지 않습니다.

이어지는 곳. 칠하기에서 출발하는 다른 문제로는 이웃끼리 다른 색을 쓰는 4색 정리⁠(four color theorem)⁠가 있고, 사람 사이의 아는 관계 전체는 좁은 세상⁠(small world)⁠ 연구의 대상입니다. 점이 자연수만큼 무한히 많으면, 변을 두 색으로 어떻게 칠해도 서로 모두 같은 색으로 이어진 무한히 많은 점들이 반드시 있습니다(무한 램지 정리⁠, infinite Ramsey theorem⁠). 이것은 가산 집합⁠(countable set)⁠에 관한 정리로, 여섯 명 논법을 끝없이 되풀이해 증명합니다. 한 점을 고르면 그 점에서 나가는 무한히 많은 변 가운데 한 색이 무한히 많으므로, 그 색 변으로 이어진 점들만 남기고 그 색을 고른 점에 적어 둡니다. 남은 점들 가운데서 또 한 점을 골라 같은 일을 한없이 이어 갑니다. 이렇게 고른 점들에 적힌 색도 둘뿐이니 어느 한 색이 무한히 많이 적혀 있고, 그 색이 적힌 점들끼리는 모두 그 색으로 이어져 있습니다.

1977년 영국의 제프 패리스와 미국의 레오 해링턴은 유한 램지 정리에 '한 색으로 이어진 점들의 개수가 그 점들의 가장 작은 번호 이상이어야 한다'는 조건 하나를 더한 명제를 내놓았습니다. 이 패리스–해링턴 정리⁠(Paris–Harrington theorem)⁠는 참이지만, 수학적 귀납법⁠(mathematical induction)⁠을 핵심으로 하는 자연수의 공리계(페아노 산술⁠, Peano arithmetic⁠) 안에서는 증명할 수 없습니다. 괴델의 불완전성 정리⁠(Gödel's incompleteness theorems)⁠가 말하는 '참이지만 증명할 수 없는 명제'가 논리학의 인공적인 문장이 아니라 자연스러운 조합론⁠(combinatorics)⁠ 명제로 나타난 첫 예로 흔히 꼽힙니다.