램지 수와 무한 램지 정리

20 Feb 2025

초록. 램지 수의 정의와, 램지 수가 잘 정의됨을 보장하는 램지 정리를 살펴보고, 이를 무한 그래프로 확장한다. 또한 콤팩트성 정리를 이용하여 무한 램지 정리로부터 유한 램지 정리를 도출하는 논증을 소개한다.

도입

문제. 6개의 정점을 가지는 완전 그래프의 간선을 빨간색 또는 파란색으로 색칠할 때, 세 변의 색이 모두 같은 삼각형이 존재함을 보이시오.

일례로 다음 그림에서는 삼각형 ACF, 그리고 삼각형 BEF가 문제의 조건을 충족한다.

풀이. 임의의 정점에서 뻗어 나오는 간선의 개수는 5개이므로, 비둘기집의 원리에 따라 그중 적어도 3개는 같은 색을 가진다. 일반성을 잃지 않고, 간선 AB, AC, AD가 모두 빨간색이라고 하자. 만약 간선 BC, CD, DB 중 어느 하나가 빨간색이라면 세 변의 색이 모두 빨간색인 삼각형이 있다. 예를 들어 BC가 빨간색이라면 삼각형 ABC가 그러하다. 한편 BC, CD, DB가 모두 파란색이라면 삼각형 BCD는 세 변의 색이 모두 파란색이다. 따라서 세 변의 색이 모두 같은 삼각형이 적어도 하나 존재한다. ■

램지 정리

위 문제의 결론은 다음과 같이 표현할 수 있다. $G$가 정점수 6 이상인 완전 그래프일 때, $G$의 간선을 빨간색이나 파란색으로 칠하면 모든 간선이 빨간색인 정점수 3 이상의 부분 완전 그래프가 존재하거나, 모든 간선이 파란색인 정점수 3 이상의 부분 완전 그래프가 존재한다.

이 결론을 일반화하여, 다음 질문을 던질 수 있다. $r, b$가 임의의 자연수라고 하자. $G$가 정점수 $j$ 이상인 완전 그래프일 때, $G$의 간선을 빨간색이나 파란색으로 칠하면 모든 간선이 빨간색인 정점수 $r$ 이상의 부분 완전 그래프가 존재하거나, 모든 간선이 파란색인 정점수 $b$ 이상의 부분 완전 그래프가 존재함이 보장되는 자연수 $j$가 존재하는가?

램지 정리에 따르면 답은 그렇다이다. 구체적으로, 그러한 $j$ 중 가장 작은 수를 $R(r, b)$로 정의할 때, 다음이 성립한다.

램지 정리. 임의의 자연수 $r, b$에 대해 $R(r, b)$가 존재한다.

증명. $r + b$에 대한 귀납법으로 증명한다. 다음이 성립함을 보이면 충분한다.

\[R(r, b) \leq R(r-1, b) + R(r, b-1)\]

$R(r-1, b) = i, R(r, b-1) = j$라고 하자. $G$가 정점수 $i + j$인 완전 그래프라고 하고, $G$의 간선이 빨간색 또는 파란색으로 색칠되었다고 하자. 임의의 정점 $v \in G$에 대해, $v$와 빨간색 간선으로 연결된 정점들이 이루는 부분 완전 그래프를 $R$, 파란색 간선으로 연결된 정점들이 이루는 부분 완전 그래프를 $B$라고 하자. 다음이 성립한다.

\[|R| + |B| + 1 = i + j\]

따라서 다음 중 하나가 성립해야 한다.

1. $|R| \geq i$
2. $|B| \geq j$

1의 경우, $R(r-1, b) = i$이므로 $R$은 모든 간선이 빨간색인 정점수 $r-1$의 부분 완전 그래프를 가지거나, 모든 간선이 파란색인 정점수 $b$의 부분 완전 그래프를 가진다. 후자의 경우 $R(r, b)$의 조건이 충족되고, 전자의 경우 해당 그래프에 $v$를 추가한 그래프가 $R(r, b)$의 조건을 충족한다. 2의 경우도 마찬가지 논리가 성립한다. ■

서두의 문제는 $R(3, 3) \leq 6$임을 시사한다. 그리고 정점수가 5인 그래프 중에서는 문제의 조건을 만족하지 않는 그래프가 있음이 알려져 있기 때문에, $R(3, 3) = 6$이다. 또한 다음이 자명하다.

• $R(r, b) = R(b, r)$
• $R(r, 2) = r$

그러나 일반적인 값에 대해 램지 수를 정확히 계산하는 것은 매우 어려운 문제이다. 그래프의 정점 수에 따라 탐색해야 하는 경우의 수가 지수적 증가보다 빠르게 증가하기 때문이다. 현재 알려진 가장 빠른 램지 수 탐색 알고리즘의 시간 복잡도는 $O(c^{n^2})$이다. $R(5, 5)$의 값을 구하는 문제는 아직도 미해결 문제이며, 다만 43 이상 48 이하라는 사실이 알려져 있다. 이에 관해 다음 일화가 전해진다.

에르되시는 이런 이야기를 한 적이 있다. 우리보다 훨씬 진보한 외계 군단이 지구에 착륙해서는, $R(5, 5)$의 값을 계산해 내놓지 않는다면 지구를 산산조각낼 것이라 말했다고 상상해 보자. 에르되시가 주장하길, 이 경우에는 우리가 가진 모든 컴퓨터와 수학자를 모아들여서 계산을 시도해 봐야 한다. 그러나 만약 그들이 요구한 값이 $R(6, 6)$이라면, 에르되시 왈 이 경우에는 외계 군단을 무찌를 계획을 세우는 편이 낫다.¹

다수의 색에 대한 램지 정리

두 가지보다 많은 색을 사용하는 경우에도 램지 정리가 성립한다. 먼저 $R(n_1, n_2, \dots, n_k) = j$를, $k$가지 색을 사용하여 정점수가 $j$인 완전 그래프의 간선을 색칠했을 때 다음 중 적어도 하나가 언제나 존재하게 되는 가장 작은 $j$로 정의하자.

• 모든 간선이 1번째 색인 정점수 $n_1$의 부분 완전 그래프
• 모든 간선이 2번째 색인 정점수 $n_2$의 부분 완전 그래프
• …
• 모든 간선이 $k$번째 색인 정점수 $n_k$의 부분 완전 그래프

예를 들어 $R(3, 3, 3) = 17$임이 알려져 있다. 이는 정점수가 17 이상인 완전 그래프의 간선을 빨간색, 파란색, 또는 노란색으로 색칠하면 세 변의 색이 모두 빨간색이거나, 파란색이거나, 노란색인 삼각형이 언제나 존재한다는 의미이다.

다수의 색에 대한 램지 정리. 임의의 자연수 $n_1, \dots, n_k$에 대해 $R(n_1, \dots, n_k)$가 존재한다.

증명. $k$에 대한 귀납법으로 증명한다. 다음이 성립함을 보이면 충분하다.

\[R(n_1, \dots, n_k) \leq R(n_1, \dots, n_{k-2}, R(n_{k-1}, n_k))\]

부등식의 우변을 $j$라고 하자. $G$가 정점수 $j$인 완전 그래프라고 하고, $G$의 간선을 $k$개의 색을 사용하여 색칠하자. 잠시 $k - 1$번째 색과 $k$번째 색을 동일시하자. 그렇다면 $j$의 정의에 의해 다음 중 적어도 하나가 $G$에 존재한다.

• 모든 간선이 1번째 색인 정점수 $n_1$의 부분 완전 그래프
• 모든 간선이 2번째 색인 정점수 $n_2$의 부분 완전 그래프
• …
• 모든 간선이 $k-2$번째 색인 정점수 $n_{k-2}$의 부분 완전 그래프
• 모든 간선이 $k - 1$번째 색 = $k$번째 색인 정점수 $R(n_{k-1}, n_k)$의 부분 완전 그래프

마지막 경우를 제외하고는 $R(n_1, \dots, n_k)$의 조건을 만족하므로, 마지막 경우만 고려하면 된다. 마지막 경우가 보장하는 부분 완전 그래프를 $H$라고 하자. $R(n_{k-1}, n_k)$의 정의에 의해 $H$는 다음 중 적어도 하나를 가진다.

• 모든 간선이 $k-1$번째 색인 정점수 $n_{k-1}$의 부분 완전 그래프
• 모든 간선이 $k$번째 색인 정점수 $n_k$의 부분 완전 그래프

각 경우가 $R(n_1, \dots, n_k)$의 조건을 만족하므로, 모든 경우에 대해 $G$는 $R(n_1, \dots, n_k)$를 만족한다. ■

에르되시-라도 화살표

지금까지 우리는 간선의 색칠을 살펴 보았다. 간선은 두 정점 사이의 관계이다. 여기서 나아가, $n$개의 정점 사이의 관계를 색칠하는 상황을 떠올릴 수 있다.

논의의 편의를 위해 몇 가지 정의를 도입하자. 먼저 집합론적 자연수의 정의를 채택하여, $n = \lbrace0, 1, \dots, n-1\rbrace$로 정의한다. 또한 다음의 표기를 도입한다.

정의. $A$가 집합일 때, 다음과 같이 정의한다.

\[A^{(n)} = \{ S: S \subset A, |S| = n \}\]

즉, 자연수 $j$에 대해 $j^{(n)}$은 $_jC_n$의 각 경우를 원소로 가지는 집합이다. 예를 들어,

\[4^{(2)} = \bigg\{ \{ 0, 1\}, \{0, 2 \}, \{0, 3\}, \{1, 2 \}, \{1, 3\}, \{2, 3\} \bigg\}\]

주어진 집합을 $m$으로 분할한다는 것은, 집합의 각 원소를 $m$개의 범주 중 하나로 분류하는 것을 말한다. 예를 들어 $4^{(2)}$를 3개로 분류한 한 가지 결과는 다음과 같다.

\[\bigg\{ \big\{ \{0, 1\}, \{ 0, 2 \}, \{1, 2\} \big\}, \big\{ \{0, 3\}, \{2, 3 \} \big\}, \big\{ \{1, 3 \} \big\} \bigg\}\]

위 분할에서 $0, 1, 2$끼리 이루어진 집합은 모두 같은 범주에 속해 있다. 이것을 두고 $0, 1, 2$는 해당 분할에 대해 동질적_homogeneous이라고 한다.

다음의 표기를 정의한다. 이 표기를 에르되시-라도 화살표_{Erdős-Rado arrow}라고 부른다.

정의. $j^{(n)}$을 $m$으로 분할할 때 동질적인 $k$개의 원소가 언제나 존재할 경우 다음과 같이 표기한다.

\[j \rightarrow (k)^n_m\]

서두의 문제는 $6 \rightarrow (3)^2_2$임을 시사한다. $n = 2$인 이유는 간선이 두 정점 사이의 관계이기 때문이고, $m = 2$인 이유는 색이 두 가지이기 때문이다.

앞서 본 램지 정리에 의해 다음이 성립한다.

\[\forall k\; \exists j: j \to (k)^2_2\]

한편 다수의 색에 대한 램지 정리는 다음을 시사한다.

\[\forall k, m \; \exists j : j \to (k)^2_m\]

일반적으로 다음이 알려져 있다.

유한 에르되시-라도 정리. 임의의 자연수 $n, m, k$에 대해, 다음을 만족하는 자연수 $j$가 존재한다.

\[j \rightarrow (k)^n_m\]

무한 램지 정리

흥미롭게도 램지 정리는 $k$가 무한 기수_cardinal일 때에도 성립한다. 다음이 알려져 있다.

에르되시-라도 정리. 임의의 기수 $\lambda$와 자연수 $n, m$에 대해, 다음을 만족하는 기수 $\kappa$가 존재한다.

\[\kappa \rightarrow (\lambda)^n_m\]

특히 다음이 성립한다.

무한 램지 정리. \(\aleph_0 \rightarrow (\aleph_0)^n_m\)

즉 힐베르트 호텔의 투숙객들이 임의로 악수를 나눌 때, 서로 모두 악수를 나눈 사람들이 무한히 많거나, 서로 전혀 악수를 나누지 않은 사람들이 무한히 많다.

위 정리에 대한 증명은 필자 뇌피셜이기 때문에 오류가 있다면 알려주길 바란다.

증명. $n = m = 2$인 경우에 대해 증명한다. $G$가 크기가 $\aleph_0$인 완전 그래프라고 하자. $G$의 간선들을 빨간색 또는 파란색으로 색칠한다. $G$의 정점 $v, w$에 대해, $\overline{vw}$가 빨간색이면 $\overline{vw} \in R$, 파란색이면 $\overline{vw} \in B$와 같이 표현하자.

임의의 $G$의 정점 $v_0$에 대해, 다음과 같이 정의하자.

\[\begin{aligned} R_1 = \{ w \in G : \overline{v_0w} \in R \}\\ B_1 = \{ w \in G : \overline{v_0w} \in B \} \end{aligned}\]

$R_1 \cup B_1 \cup \lbrace v_0 \rbrace = G$이므로, $R_1$과 $B_1$ 중 적어도 하나는 무한집합이다. 만약 $R_1$이 무한집합이라면 $v_0 \in R$와 같이 표기하고, $B_1$이 무한집합이라면 $v_0 \in B$와 같이 표기하자.

$R_1$이 무한집합이라고 가정하자. 선택 공리로부터 $R_1$의 원소 $v_1$을 선택할 수 있다. 이제 다음과 같이 정의하자.

\[\begin{aligned} R_2 = \{ w \in R_1 : \overline{v_1w} \in R \}\\ B_2 = \{ w \in R_1 : \overline{v_1w} \in B \} \end{aligned}\]

$R_2 \cup B_2 \cup \lbrace v_1\rbrace = R_1$이므로, $R_2$와 $B_2$ 중 적어도 하나는 무한집합이다. 마찬가지로 $R_2$가 무한집합이라면 $v_1 \in R$, $B_2$가 무한집합이라면 $v_1 \in B$와 같이 표기하자.

$B_2$가 무한집합이라고 가정하자. $B_2$의 원소 $v_2$를 선택하여 다음과 같이 정의하자.

\[\begin{aligned} R_3 = \{ w \in B_2 : \overline{v_2w} \in R \}\\ B_3 = \{ w \in B_2 : \overline{v_2w} \in B \} \end{aligned}\]

이같은 식으로 반복함으로써 다음의 정점열을 얻는다.

\[V = \{ v_0, v_1, v_2, v_3, \dots \}\]

각 $v \in V$에 대해 $v \in R$ 또는 $v \in B$이다. $V$가 무한집합이므로, 다음 중 하나는 무한집합이다.

\[\begin{aligned} H = \{ v \in V : v \in R \} \\ K = \{ v \in V : v \in B \} \end{aligned}\]

만약 $H$가 무한집합이라면 $H$의 정점들이 이루는 완전 그래프는 간선의 색이 모두 빨간색이다. 한편 $K$가 무한집합이라면 $K$의 정점들이 이루는 완전 그래프는 간선의 색이 모두 파란색이다. 따라서 $\aleph_0 \rightarrow (\aleph_0)^2_2$이다. ■

따름정리. $A$가 $\mathbb{N}$의 무한 부분집합일 때, 어떤 $A$의 무한 부분집합 $B$가 존재하여 다음 중 하나가 성립한다.

• 임의의 $b \in B$에 대해, $c$가 $b$보다 큰 $B$의 원소라면 $b \mid c$이다.
• 임의의 $b, c \in B$에 대해, $b \nmid c, c \nmid b$이다.

증명. $k = A$로 잡고, $x < y$에 대해 $x \mid y$라면 $\lbrace x, y \rbrace$를 1번 범주로, 그렇지 않으면 2번 범주로 분류하는 분할을 고려한 뒤 $\aleph_0 \rightarrow (\aleph_0)^2_2$임을 사용한다. ■

무한에서 유한으로

흥미롭게도 콤팩트성 정리를 사용하면 무한 램지 정리로부터 유한 램지 정리를 증명할 수 있다. 즉, 다음이 성립한다.

보조정리. $\aleph_0 \rightarrow (\aleph_0)^n_m$라면, 임의의 자연수 $k$에 대해 $j \to (k)^n_m$을 만족하는 자연수 $j$가 존재한다.

증명. $n = 2$일 때를 증명한다. 간선이 $m$가지 색으로 색칠된 그래프는 다음과 같이 형식화할 수 있다. 먼저 언어 $\mathcal{L} = (V, f, 1, 2, \dots, m)$의 부호수_signature을 다음과 같이 정의한다.

• $V$는 단항 관계이다.
• $f$는 이변수 함수이다.
• $1, 2, \dots, m$은 상수이다.

$T$가 다음으로 이루어진 $\mathcal{L}$-이론이라고 하자.

• $\psi : \lnot V(1) \land \lnot V(2) \land \lnot V(m)$
• $\theta : \forall x, y \; (V(x) \land V(y) \land x \neq y) \rightarrow ( f(x, y) = 1 \lor f(x, y) = 2 \lor \cdots \lor f(x, y) = m )$
• $\phi_1 : \exists x_1, x_2 \; V(x_1) \land V(x_2) \land x_1 \neq x_2$
• $\phi_2 : \exists x_1, x_2, x_3 \; V(x_1) \land V(x_2) \land V(x_3) \land x_1 \neq x_2 \land x_2 \neq x_3 \neq x_1 \neq x_3$
• 각 $n \in \mathbb{N}$에 대해, $\phi_n$

$\psi$는 $1, 2, \dots, m$이 정점이 아니라 색을 표현한다는 의미이다. $\theta$는 임의의 두 정점 간 간선이 $1$부터 $m$ 중 하나의 색을 가짐을 의미한다. 그리고 $\phi_n$은 적어도 $n$개의 정점이 존재한다는 의미이다. 임의의 $n$에 대해 $\phi_n \in T$이므로, $T$의 모델은 무한 완전 그래프이다.

다음의 문장을 $\chi$라고 하자.

\[\exists x_1, x_2, \dots, x_k : f(x_1, x_2) = f(x_1, x_3) = \dots = f(x_{k-1}, x_k)\]

즉, $\chi$는 정점수 $k$인 동색의 부분 완전 그래프가 존재한다는 의미이다. 따라서 무한 램지 정리에 따라 다음이 성립한다.

\[T \vDash \psi\]

그리고 콤팩트성 정리에 따라 어떤 유한 부분이론 $T’ = \lbrace \psi, \chi, \phi_1, \dots, \phi_j \rbrace$가 존재하여 다음이 성립한다.

\[T' \vDash \psi\]

즉, 정점수 $j$ 이상인 모든 완전 그래프는 $\psi$를 만족한다. 다시 말해, $j \to (k)^2_m$이다. 임의의 $n$에 대해서 증명하려면 $R$을 $n$항 관계로 두면 된다. ■

¹ Joel H. Spencer (1994), Ten Lectures on the Probabilistic Method