파티 플래너 문제와 램지 수

 

여러분은 파티를 준비하고 있고, 초대할 손님 명단을 작성 중입니다. 파티가 즐겁게 진행되려면 몇 명을 초대해야 할까요? 여기서 핵심은 초대된 사람들 사이의 관계입니다. 모든 손님이 서로 잘 아는 사이라면 이야깃거리가 금방 고갈될 수 있습니다. 반대로, 모든 손님이 서로 모르는 사이라면 어색한 분위기가 형성될 수도 있죠. 따라서, 손님들 사이의 관계가 적당히 섞여 있는 것이 중요합니다. 그렇다면, 이 균형을 유지하면서도 파티가 흥미롭게 진행되려면 어떻게 해야할까요?

 

이런 질문을 던져봅시다. 적어도 3명이 서로 알거나, 3명이 서로 모르는 그룹이 생기도록 하려면 최소 몇 명의 손님을 초대해야 할까요?

 

파티 플래너 문제와 그래프

앞서 본 문제를 파티 플래너 문제라고 부릅니다. 이 문제를 이해하기 위해서는 그래프 이론을 사용해야 합니다. 그래프 이론은 복잡한 관계를 시각적으로 나타내고 분석할 수 있는 강력한 도구입니다.

 

예를 들어, 손님을 점(node)으로, 두 손님의 관계를 선(edge)으로 표현하면, 문제를 시각적으로 간단하게 표현할 수 있습니다. 그리고 이러한 그래프 모델은 다양한 크기의 문제로 확장 가능합니다.

 

먼저 5명의 손님을 원형으로 배치하고, 각 손님들 사이의 관계를 표시해보겠습니다. 아는 사람들 사이의 관계는 파란색 선으로, 모르는 사람들 사이의 관계는 빨간색 선으로 나타냅니다.[^1]

 

 

이 그래프에서 각 손님은 서로 아는 관계(파란색 선)와 모르는 관계(빨간색 선)로 연결되어 있습니다. 예를 들어, 1번 손님과 2번, 5번 손님은 서로 아는 사이입니다(파란색 선). 반면, 1번 손님과 3번, 4번 손님은 서로 모르는 사이입니다(빨간색 선).

 

파란색 선으로 연결된 사람들은 서로 알고 있지만, 같은 색 선으로 둘러싸인 삼각형이 없습니다. 예를 들어, 1번, 2번, 3번 손님은 1번과 2번, 2번과 3번이 서로 아는 사이지만, 1번과 3번은 서로 모르는 사이입니다(빨간색 선). 따라서 파란색 선으로만 이루어진 삼각형이 없습니다.

반대로, 1번, 3번, 4번 손님은 1번과 3번, 1번과 4번이 서로 모르는 사이지만, 3번과 4번은 서로 아는 사이입니다(파란색 선). 따라서 빨간색 선으로만 이루어진 삼각형도 없습니다.

 

따라서, 5명의 손님을 초대했을 때는 어떤 3명이 서로 모두 아는 친구이거나, 3명이 서로 모르는 낯선 사람인 상황이 그림과 같이 발생할 수 없을 수도 있습니다.

 

그러나 6명일 때는 다릅니다. 정말 신기하게도, 6명을 초대하면 손님들 사이의 관계를 어떻게 설정하더라도, 서로 아는 3명의 그룹 또는 서로 모르는 3명의 그룹 중 하나가 반드시 발생하게 됩니다. 지금부터 그 이유를 설명해드리겠습니다.

 

램지 수 $R(s, t)$

증명에 앞서, 파티 플래너 문제를 수학적으로 재해석해 보겠습니다. 앞선 질문은 질문은 램지 수 $R(s, t)$라는 개념으로 설명할 수 있습니다. 여기서 $R(s,t)$란, 임의의 완전 그래프에서 $s$개의 정점이 모두 연결된 클리크 또는 $t$개의 정점이 모두 연결되지 않은 독립 그래프를 반드시 포함하도록 하는 최소한의 정점 수 $N$입니다.[^2] 여기서 완전 그래프 $K_n$이란모든 정점이 연결된 그래프를 의미합니다. $K_3$는 $3$개의 정점이 모두 서로 연결된 삼각형 모양의 그래프이고, $K_4$는 $4$개의 정점이 모두 서로 연결된 그래프입니다.

 

 

반대로, 그래프 내의 모든 정점이 서로 연결되지 않은 그래프를 독립 그래프라고 합니다. 독립 그래프에서는 어떤 두 정점 사이에도 간선이 존재하지 않습니다.

이해하기 쉽게 연결된 선은 파란색으로, 연결되지 않은 선은 빨간색 선으로 나타내 보겠습니다.

 

그렇다면, $R(s,t)$는 그래프의 모든 변을 두 가지 색으로 색칠했을 때, $s$개의 꼭짓점이 파란색으로 완전 연결되거나, $t$개의 꼭짓점이 빨간색으로 완전 연결되도록 하는 최소한의 정점 수입니다. 따라서 앞서 보았던 문제 상황은 '$R(3,3)$이 몇 인가?'하는 문제로 바뀌게 되죠.

 

다시 말해, 모든 변의 색이 같은 삼각형이 존재하는 모든 정점들이 서로 연결된 최소의 정점 그래프를 찾으면 됩니다. 앞서 $n=5$일 때, 이러한 성질을 만족하지 않는 예시를 찾았으므로, $n=6$일 때는 이러한 성질을 반드시 만족하는지, 찾아보도록 하겠습니다.

 

먼저 $6$개의 정점을 가지는 완전 그래프 $K_6$을 상상해보겠습니다.

 

비둘기집 원리

완전 그래프 $K_6$의 특정 꼭짓점에서 나가는 $5$개의 선 중 적어도 $3$개의 선은 비둘기 집 원리에 의해 반드시 같은 색으로 칠해져야 합니다. 왜냐하면 빨강과 파랑 두개의 색에 $5$개의 선을 골고루 배정한다면, 아무리 골고루 배정 해도 하나가 남고, 그 하나는 반드시 두 색 중 하나의 색을 골라야하기 때문이죠. 저는 이 선이 파란색으로 같다고 하고, $2, 3, 4$로 그어보겠습니다.

단색 삼각형의 존재

이제 선택 받은 $3$개의 꼭짓점 $2,3, 4$를 연결 하는 선 $2-3,3-4,2-4$ 중 적어도 하나의 선이 파란 색이라면 단색 삼각형이 완성됩니다.

 

 

만약 세 선분이 모두 파란색이 아니라면, 반대로 모두 빨간색이어야 하는데, 그렇다면 $2,3,4$ 세 개의 꼭짓점을 연결하는 모든 선은 빨간색으로 칠해져 다시 단색 삼각형이 만들어집니다.

 

색 교환 가능성

이 논리는 특정 색을 임의로 선택했기 때문에, 파란색과 빨간색의 역할을 교환해도 동일하게 적용됩니다. 따라서, 어떠한 경우에도 단색의 삼각형이 존재한다는 것을 보여줍니다. $6$개의 정점을 가지는 그래프에서는 항상 단색 삼각형이 존재함을 증명했으므로, $R(3, 3) \leq 6$이고, 이전 그래프로 부터 $R(3, 3) > 5$임으로, $R(3, 3)=6$입니다.

 

램지 이론(Ramsey Theory)

파티 플래너 문제는 겉보기에는 단순해 보이지만, 사실 매우 복잡한 문제입니다. 왜냐하면, $n$개의 정점을 가진 그래프는 ${}_{n} \rm{C}_{2}$개의 선을 갖기 때문이죠. 각 간선을 두 가지 색으로 칠할 수 있으므로 가능한 색칠의 수는 $2^{{}_{n} \rm{C}_{2}}$이 됩니다. 정점의 수가 증가할 때마다 가능한 모든 간선의 색칠 조합이 지수적으로 증가하죠.

 

$$\begin{array}{c|c|c}

n & 2^{\binom{n}{2}} & \text{Value} \\

\hline

4 & 2^6 & 64 \\

5 & 2^{10} & 1024 \\

6 & 2^{15} & 32768 \\

7 & 2^{21} & 2097152 \\

8 & 2^{28} & 268435456 \\

9 & 2^{36} & 68719476736 \\

10 & 2^{45} & 35184372088832 \\


\end{array}$$

 

단적으로 앞선 상황을 일일이 확인한다면, 정점이 $6$개인 $3$만 가지가 넘는 $K_6$ 그래프마다 단색 삼각형이 반드시 존재하는지 확인해봐야합니다. 램지 수를 계산하는 것은 간단한 아이디어에서 시작되지만, 실제로 계산하는 과정은 매우 복잡하고 시간이 많이 걸리는 문제입니다. 만약 그래프의 정점의 개수가 $10$개만 되더라도, $35$조 가지가 넘는 경우의 수를 따져봐야하죠. 왜냐하면, 문제의 핵심은 특정한 부분 그래프가 항상 존재하도록 보장하는지 찾아야 하기 때문입니다.

 

그래도 다행인 점은 자연수 $s$와 $t$가 커지더라도 램지 수 $R(s, t)$는 반드시 존재한다는 것입니다. 프랭크 램지는 자신의 논문 On a Problem of Formal Logic[^4]을 통해 오늘날 램지 이론으로 알려진 개념을 처음 제시했습니다. 램지는 특정 논리적 문제를 해결하는 과정에서 조합적 방법론을 사용했으며, 이 과정에서 그래프 이론과 조합론에서 필수적인 램지 이론을 도출했습니다.

[!note] On a Problem of Formal Logic의 개요
1. 무한 집합에 대한 정리 (Theorem A)

램지는 논문의 첫 번째 부분에서 무한 집합 $F$와 그 하위 집합의 $r$-조합에 대한 문제를 다룹니다. 이 정리는 무한 집합 $F$의 모든 $r$-조합이 임의의 방식으로 서로 배타적인 $\mu$개의 클래스 $C_i$로 나뉘었을 때, 반드시 같은 클래스에 속하는 무한 하위 집합 $A$가 존재함을 보장합니다.

램지는 귀납법을 사용하여, 가장 간단한 경우(예: $r = 1$)에서 출발해 점진적으로 더 복잡한 경우로 증명을 확장합니다. $\mu = 2$인 경우부터 시작해 증명을 전개하며, 무한 하위 집합에서 이러한 패턴이 반드시 나타날 수밖에 없음을 논증합니다.

2. 유한 집합에 대한 정리 (Theorem B)

무한 집합에 대한 정리를 바탕으로, 램지는 유한 집합 $T_m$에 대한 조합적 정리로 확장합니다. 이 정리는 주어진 $m$개의 정점을 가진 유한 집합 $T_m$에서, 모든 $r$-조합이 임의로 $\mu$개의 서로 배타적인 클래스 $C_i$로 나뉘었을 때, 동일한 클래스에 속하는 하위 집합이 반드시 존재함을 보장합니다.

이 정리도 마찬가지로 귀납법을 사용하여 증명되며, 무한 집합의 경우에서 유한 집합으로 귀납적으로 확장하는 방식으로 논리가 전개됩니다. 램지는 이를 통해 논리적 문제 해결의 중요한 도구로 이 정리를 활용할 수 있음을 보여줍니다.

3. 논리 공식의 일관성 결정

램지는 논리 공식을 평가하는 문제를 다루며, 주어진 공식이 일관성을 가지는지 여부를 결정하는 절차를 제시합니다. 이 과정에서 Theorem B를 사용하여, 특정 논리 공식이 모든 가능한 해석에서 참인지, 또는 그 공식이 어떤 경우에도 거짓이 될 수 없는지 여부를 결정하는 방법을 설명합니다.

램지는 이 이론을 활용하여 다양한 논리 공식을 평가할 수 있는 방법을 제안하며, 특히 유한한 개체로 구성된 우주에서 이러한 일관성을 확인하는 데 필요한 조건을 도출합니다.

4. 유한 집합에서의 문제 해결

유한 집합의 크기에 따라 논리 공식의 일관성을 판단하는 조건을 제시합니다. 특히, 주어진 논리 공식이 특정 크기의 유한 집합에서 일관성을 유지하기 위해 필요한 최소한의 조건을 설정합니다.

공식의 일관성을 보장하기 위해 필요한 최소 크기의 집합 $m_0$를 계산하는 문제를 다룹니다. 이 조건은 주어진 공식이 무한한 집합에서뿐만 아니라, 특정 크기의 유한 집합에서도 일관성을 유지할 수 있는지를 판단하는 데 사용됩니다.

 

램지는 논문의 초반에서 무한 집합에 대한 정리를 하며 무한 집합에서 임의의 방식으로 하위 집합을 분할할 때, 반드시 특정 패턴이 나타나는 하위 집합이 존재한다는 것을 보여주었습니다. 이후 무한 집합에 대한 정리를 유한 집합의 경우로 확장하면서, 충분히 큰 구조(여기서는 그래프) 내에서 반드시 특정한 하위구조가 나타날 수밖에 없음을 증명했습니다. 이러한 결과는 무작위적 구조에서도 특정 패턴이 반드시 나타난다는 것을 수학적으로 보장해줍니다. 다른 말로, 특정한 크기 이상이 되면 반드시 어떤 형태의 질서가 나타날 수밖에 없다는 것을 보여주며, 완전한 불규칙은 존재할 수 없다는 것을 증명낸거죠. 무작위성 속에서도 예측 가능한 구조가 존재함을 보여주는 이 정리는 네트워크 이론, 데이터 분석, 컴퓨터 과학 등 다양한 분야에서 응용되고 있습니다.

[! note] 램지의 생애
프랭크 플럼튼 램지(Frank Plumpton Ramsey)는 1903년에 태어나 1930년에 불과 26세의 나이로 세상을 떠난 영국의 수학자, 철학자, 경제학자였습니다. 그의 짧은 생애에도 불구하고, 그는 수학과 철학, 특히 확률론과 경제 이론에 지대한 영향을 미쳤습니다.

램지는 1920년대 초반부터 수학과 철학, 그리고 경제학에 걸쳐 뛰어난 연구를 수행했습니다. 그는 1926년에 “확률과 진리”라는 논문을 통해 주관적 확률과 유틸리티 이론의 기초를 다졌으며, 이 이론은 나중에 게임 이론과 의사결정 이론에서 핵심 개념으로 자리 잡았습니다. 그의 작업은 이후 존 폰 노이만과 오스카 모르겐슈테른의 게임 이론에서도 큰 영향을 미쳤습니다. 또한 베르트랑 러셀의 논리적 원자론을 발전시키고, 의미론적 이론에 중요한 기여를 했습니다. 램지의 논리학적 작업은 철학과 수학의 경계를 허물며, 이후 수많은 철학적 논의의 기초가 되었습니다.

램지의 경제학적 기여로는 “주관적 유틸리티의 극대화”라는 개념을 통해 개인의 경제적 선택이 어떻게 이루어지는지를 설명했습니다. 또한 이자율에 대한 연구를 통해 자본 축적의 원리와 관련된 중요한 통찰을 제공했습니다. 그의 경제 이론은 나중에 케인즈 경제학의 중요한 기초가 되었으며, 현대 거시경제학에서도 여전히 중요한 위치를 차지하고 있습니다.

램지의 죽음은 오래전부터 미스터리로 남아 있었습니다. 그의 마지막 병세와 관련된 여러 가지 가능성이 제기되었지만, 최근의 연구에서는 그가 겪었던 일련의 병증이 복잡한 상태였음을 시사합니다.(그의 사망 원인으로는 감염성 질환인 바이엘 병(Weil’s disease), 자가면역 질환인 원발성 경화성 담관염(Primary Sclerosing Cholangitis), 그리고 담석(Gallstones) 으로 인한 합병증 등이 제안되었습니다.) 램지의 상태는 1929년 말부터 급격히 악화되었고, 결국 1930년 1월 19일에 사망에 이르게 되었습니다

더 많은 사람을 초대한다면?

이후 에르되시(Erdős)와 셀프린스(Szekeres) 등의 수학자들은 램지 이론을 확장하고, 특정 램지 수에 대한 경계를 계산하는 연구를 진행했습니다. $R(3, 3) = 6$이라는 결론은 비교적 간단하게 나왔지만, 만약 $R(4, 3)$은 어떨까요? 가장 쉬운 방법은 정점을 하나씩 늘려가며 안되는 예시를 찾거나, 모든 그래프를 다 확인하는 방법일 것입니다. 물론 많은 수학자들이 도전하고 있지만 쉬운일은 아닙니다. 이러한 작업은 엄청난 계산을 요구하며, 현재의 컴퓨터 기술로도 정확한 값을 구하는 것이 어려운 상황입니다.

 

 

당장 $R(4, 3)$만 하더라도 $9$개의 정점이 필요하고, $R(4, 4)$는 $18$로 훨씬 더 큰 수입니다. 심지어 $R(5, 5)$는 $43$부터 $48$까지의 정수라는 상한과 하한은 알지만 정확히 몇 개가 필요한지는 아직도 미해결 문제입니다.[^3]

 

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
s \backslash t & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\hline
2 & & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
3 & & & 6 & 9 & 14 & 18 & 23 & 28 & 36 & 40-41 \\
\hline
4 & & & & 18 & 25 & 36-40 & 49-58 & 59-79 & 73-106 & 92-136 \\
\hline
5 & & & & & 43-48 & 59-85 & 80-133 & 101-194 & 133-282 & 149-381 \\
\hline
6 & & & & & & 102-161 & 115-273 & 134-427 & 183-656 & 204-949 \\
\hline
7 & & & & & & & 205-497 & 219-840 & 252-1379 & 292-2134 \\
\hline
8 & & & & & & & & 282-1532 & 329-2683 & 343-4432 \\
\hline
9 & & & & & & & & & 565-5366 & 581-9797 \\
\hline
10 & & & & & & & & & & 798-17730 \\
\hline
\end{array}$$

 

램지 수의 계산은 아직도 수많은 미해결 문제를 남기고 있으며, 수학자들과 컴퓨터 과학자들의 호기심을 자극하고 있습니다. 이 문제를 해결하려는 노력은 단순히 수학적 아름다움 때문만이 아니라, 그래프 이론의 발전과 알고리즘 개선에 큰 기여를 할 수 있기 때문입니다. 정확한 값을 알아내기 위해 여러분은 어떤 전략을 사용하실건가요? 미지의 영역을 탐험해 볼 의향이 있으신가요?

 

[^1]: Ramsey Graphs
[^2]: Ramsey Numbers, Christos Nestor Chachamis, 2018
[^3]: Array of Ramsey numbers R(n,k), A212954 - OEIS
[^4]: ON A PBOBLEM OF FORMAL LOGIC, F. P. KAMSEY, 1928