램지 이론: 무질서 속에서도 반드시 규칙은 나타난다—

1. 6명이 모이면 반드시 발견되는 3인조

파티에 6명이 모였다고 가정해 봅시다. 오랜 친구도 있을 것이고 처음 만난 사람도 있을 것입니다. 누구와 누가 아는 사이인지는 아무리 복잡하게 얽혀 있어도 상관없습니다. 그럼에도 불구하고 다음 중 하나는 반드시 성립합니다.

3명 중 어떤 2명을 선택해도 서로 아는 사이이다.
3명 중 어떤 2명을 선택해도 서로 모르는 사이이다.

‘대체로 발견된다’는 뜻이 아닙니다. 관계를 어떻게 구성하더라도 예외 없이 성립합니다. 게다가 6명이라는 수는 최소입니다. 5명이라면 두 가지 3인조를 모두 만들지 않는 배치가 가능합니다.

이 작은 놀라움이 램지 이론 으로 들어가는 입구입니다. 거대한 구조를 아무리 복잡하게 나누더라도, 충분한 크기만 있다면 조건을 만족하는 작은 구조를 완전히 피할 수는 없습니다. 이러한 ‘피할 수 없는 규칙성’을 다룹니다.

다만, 무질서 속에 원하는 어떤 규칙이든 다 나타난다는 뜻은 아닙니다. 무엇을 대상으로 하고 몇 가지로 분류하며 어떤 형태를 찾을 것인지를 정해야 비로소 수학적인 주장이 됩니다. 먼저 종이에 6개의 점을 찍어볼 수 있는 친숙한 예시부터 시작해 봅시다.

2. 인간관계를 빨간색과 파란색 선으로 바꾸기

모델의 전제 조건

이 글에서는 ‘아는 사이’를 대칭적인 관계로 간주합니다. A가 B를 안다면 B도 A를 알며, 각 쌍은 ‘아는 사이’인지 ‘모르는 사이’인지 둘 중 하나로 반드시 분류할 수 있다고 가정합니다.

일방적으로 이름만 알고 있는 관계나 아는 사이인지 불분명한 관계는 이 모델에 포함하지 않습니다. 또한 ‘모르는 사이’가 ‘싫어한다’거나 ‘적대한다’는 의미는 아닙니다.

사람을 점으로, 두 사람의 관계를 선으로 나타냅니다.

그림 요소	의미
점 (꼭짓점)	참가자 1명
빨간 실선	두 사람이 서로 아는 사이
파란 점선	두 사람이 서로 모르는 사이
같은 색의 세 변으로 이루어진 삼각형	찾고자 하는 3인조

모든 사람의 모든 쌍을 연결하므로 이것은 완전 그래프 입니다. 꼭짓점이 $n$ 개인 완전 그래프를 $K_n$ 이라고 쓰며, 변의 수는 다음과 같습니다.

$$ \binom{n}{2}=\frac{n(n-1)}{2} $$

6명이라면 15개의 변이 있습니다. ‘A가 B와 C를 안다’는 사실만으로는 세 사람이 서로 아는 사이가 된다고 보장할 수 없습니다. B와 C 사이도 빨간색이어야 합니다. 삼각형의 세 변 모두 가 같은 색이어야 한다는 조건을 잊지 마세요.

이후로는 모두 빨간색이거나 모두 파란색인 삼각형을 단색 삼각형 이라고 부릅니다. 색을 구별하기 어려운 환경에서도 알아볼 수 있도록 그림에서는 빨간색을 실선, 파란색을 점선으로 표시합니다.

3. 6명이면 반드시 존재함을 증명하기

이 증명에서 사용하는 도구는 비둘기집 원리뿐입니다. ‘5개의 물건을 2가지로 나누면 적어도 한쪽에는 3개가 있다’는 매우 소박한 사실을 사용합니다.

1단계: 한 사람에게만 집중하기

6명 중 임의의 한 사람을 A라고 합니다. A에게서는 나머지 5명을 향해 5개의 선이 뻗어 나옵니다. 각각 빨간색 또는 파란색이므로, 적어도 3개는 같은 색을 가집니다.

$$ \left\lceil\frac{5}{2}\right\rceil=3 $$

여기서 $\lceil x\rceil$ 는 $x$ 이상의 가장 작은 정수(올림 함수)를 나타냅니다. 빨간색도 파란색도 2개 이하라면 합해서 4개 이하밖에 되지 않아 5개의 선을 칠할 수 없다고 생각해도 같습니다.

빨간색 선이 3개 이상인 경우를 생각하고, 그 선들이 연결된 세 사람을 B, C, D라고 부릅시다. A–B, A–C, A–D는 모두 빨간색입니다. 처음에 파란색 선이 3개 이상 발견된 경우라면 아래의 빨간색과 파란색을 바꾸기만 하면 동일한 논리가 성립합니다.

2단계: B·C·D 사이를 살펴보기

B–C, B–D, C–D의 3개 선에 대해서는 두 가지 경우밖에 없습니다.

경우 ①: 빨간색 선이 적어도 1개 있다. 예를 들어 B–C가 빨간색이라면, A–B와 A–C도 빨간색이므로 A·B·C가 빨간색 삼각형을 이룹니다. 다른 두 선이 어떤 색이든 상관없습니다.

경우 ②: 빨간색 선이 하나도 없다. 그러면 B–C, B–D, C–D는 모두 파란색입니다. 이번에는 B·C·D가 파란색 삼각형을 이룹니다.

A에서 같은 색의 선 3개를 고르고, 그 끝에 있는 3명 사이에 빨간색이 있으면 빨간 삼각형, 없으면 파란 삼각형이 완성되는 증명 그림

그림에서 회색 변과 생략된 변은 증명 과정에서 색을 결정할 필요가 없는 부분입니다. 실제 완전 그래프에서는 그 변들에도 빨간색이나 파란색 중 하나가 칠해져 있습니다.

이것으로 어떤 방식으로 색을 칠하더라도 단색 삼각형이 존재함을 알 수 있습니다. 15개의 변을 전부 조사할 필요는 없습니다. 한 사람에게서 나오는 5개의 선과 그 앞의 3명 사이의 관계만으로 모든 가능성을 빠짐없이 다룬 것입니다. 대학 교재 해설

4. 왜 5명으로는 부족할까?

‘6명이면 충분하다’와 ‘6명이 최소이다’는 서로 다른 주장입니다. 최소임을 보이려면 5명일 때 조건을 만족하지 않는 반례를 하나 제시해야 합니다.

5명을 정오각형의 꼭짓점에 배치합니다. 이웃한 사람들끼리, 즉 오각형의 둘레에 해당하는 5개의 변을 빨간색으로 칠합니다. 나머지 대각선 5개는 모두 파란색으로 칠합니다.

오각형의 둘레를 빨간색, 대각선을 파란색으로 칠한 5명의 반례. 어느 색상에도 삼각형이 없다

빨간색만 보면 오각형을 한 바퀴 도는 고리 모양입니다. 3명을 어떻게 선택하더라도 빨간색 변만으로 삼각형을 닫을 수는 없습니다. 파란색만 보면 별 모양이지만 꼭짓점을 따라가는 순서를 바꾸면 이 역시 5개의 꼭짓점을 한 바퀴 도는 고리 형태입니다. 파란색에도 삼각형은 존재하지 않습니다.

별 모양 선들의 교차점은 새로운 꼭짓점이 아닙니다. 사람에 대응하는 것은 A부터 E까지의 5개 점뿐입니다. 선의 교차로 인해 작은 삼각형이 보이더라도, 그것은 이 문제에서 세는 삼각형이 아니라는 점에 주의해야 합니다.

빨간색 3인조도 파란색 3인조도 피할 수 있으므로 5명으로는 보장할 수 없습니다. ‘6명이면 반드시 성립한다’는 사실과 결합하여 최소 인원수가 6명임이 확정됩니다.

5. 이 ‘최소의 크기’를 램지 수라고 부른다

완전 그래프의 변을 빨간색과 파란색으로 칠했을 때, 빨간색 $K_s$ 또는 파란색 $K_t$ 가 반드시 나타나는 최소의 꼭짓점 수를 램지 수 $R(s,t)$ 라고 씁니다.

빨간색 $K_s$ 란 선택된 $s$ 개의 꼭짓점 사이의 모든 변이 빨간색인 것을 말합니다. 단순히 빨간색 경로로 연결되어 있는 것만으로는 부족합니다. $K_3$ 은 삼각형이므로, 지금까지의 결론은 다음 한 줄로 요약됩니다.

$$ R(3,3)=6 $$

램지의 정리(Ramsey’s Theorem)는 고정된 유한한 $s, t$ 에 대해 이러한 유한한 수가 항상 존재한다고 말합니다. 하지만 ‘존재한다’는 사실과 ‘최솟값을 쉽게 구할 수 있다’는 것은 다릅니다. 삼각형에 대한 증명은 짧지만, 찾고자 하는 단색 부분 그래프의 크기를 키우면 계산은 급격히 어려워집니다.

기본적인 상계에는 다음과 같은 관계식이 성립합니다.

$$ R(s,t)\leq R(s-1,t)+R(s,t-1) \qquad(s,t\geq3) $$

우변을 $N$ 이라 두고, $N$ 개의 꼭짓점 중 하나를 선택합니다. 그 꼭짓점에서 빨간색으로 연결된 꼭짓점이 $R(s-1,t)$ 개 이상 있다면, 그 안에 빨간색 $K_{s-1}$ 또는 파란색 $K_t$ 가 존재합니다. 전자의 경우라면 원래의 꼭짓점을 더해 빨간색 $K_s$ 를 만들 수 있습니다. 후자의 경우라면 그대로 목표가 달성됩니다.

빨간색으로 연결된 꼭짓점이 그만큼 많지 않다면 파란색으로 연결된 꼭짓점이 $R(s,t-1)$ 개 이상 존재합니다. 같은 논리를 반대 색상에 적용하면 됩니다. 이것 역시 ‘한 점에 주목하여 같은 색의 이웃을 모은다’는 증명 기법의 확장입니다.

경계값인 $R(2,t)=t$ 와 $R(s,2)=s$ 에서 출발하면 이 관계식을 통해 유한한 상계를 차례대로 구할 수 있습니다. 다만 부등호이므로 이렇게 얻은 수가 최솟값이라는 보장은 없습니다. ‘보장할 수 있는 크기’와 ‘실제로 필요한 최솟값’을 구별하는 것이 중요합니다.

6. ‘거의 반드시’와 ‘예외 없이 반드시’의 차이

이번에는 실험으로서 각 변을 서로 독립적으로 $1/2$ 의 확률로 빨간색 또는 파란색으로 칠한다고 가정해 봅시다. 이 확률 모델은 증명 자체에는 필요하지 않지만, 결과의 차이를 살펴보는 데 도움이 됩니다.

꼭짓점에 A, B, C……와 같이 이름을 붙인 채로 세면 색칠의 총 가짓수는 다음과 같습니다. 회전하거나 이름을 바꾸어 같은 형태가 되는 것도 서로 다른 색칠로 셉니다.

$$ 2^{\binom{n}{2}} $$

6명이라면 $2^{15}=32768$ 가지입니다. 3~6명에 대해 전수 조사를 진행하면 다음과 같은 결과가 나옵니다.

인원수	색칠의 총 가짓수	단색 삼각형이 없는 경우	단색 삼각형이 존재하는 비율
3명	8	6	25.00%
4명	64	18	71.88%
5명	1024	12	98.83%
6명	32768	0	100.00%

3~6명에서 단색 삼각형이 존재하는 비율 비교. 5명에서는 98.83%이지만 12가지 반례가 남고, 6명에서는 100%가 된다

5명이라도 무작위로 칠하면 약 98.83%의 확률로 단색 삼각형이 나타납니다. 몇 번 실험해보는 것만으로는 “5명이어도 반드시 존재한다"고 착각할 수 있습니다. 하지만 1,024가지 중 12가지의 반례가 엄연히 남아 있습니다. 확률이 높다는 것과 반례가 단 하나도 없다는 것 사이에는 명확한 차이가 존재합니다.

이 표는 독립적이고 동일한 확률로 칠했을 때의 비율입니다. 현실의 인간관계가 독립적으로 반반씩 발생한다고 주장하는 것은 아닙니다. 반면 6명에 대한 정리는 확률에 의존하지 않으므로, 아무리 편향된 관계라도 예외 없이 성립합니다.

평균적으로는 몇 개나 발견될까?

고정된 3개의 꼭짓점에는 3개의 변이 있으며 색칠 방법은 8가지입니다. 그중 모두 빨간색인 경우와 모두 파란색인 경우의 2가지가 단색이므로 확률은 $1/4$ 입니다. 단색 삼각형의 개수를 $T$ 라고 하면, 기댓값의 선형성에 의해 다음과 같습니다.

$$ E[T]=\binom{n}{3}\frac14 $$

6명인 경우 평균 5개입니다. 삼각형끼리는 변을 공유하므로 독립이라고 단정할 수는 없지만, 기댓값을 더하는 데에는 독립성이 필요하지 않습니다.

하지만 평균이 양수라고 해서 모든 색칠에 반드시 존재한다고 말할 수는 없습니다. 5명일 때의 평균도 2.5개이지만 0개인 반례가 존재합니다. ‘평균’과 ‘최악의 경우’를 혼동하지 않는 것 역시 램지 이론이 전해주는 중요한 관점입니다.

7. Python으로 32,768가지 경우 확인하기

다음 코드는 표준 라이브러리만으로 동작합니다. 빨간색을 0, 파란색을 1로 두고 각 변의 색을 이진수의 각 자릿수에 대응시킵니다. 3개의 꼭짓점을 골라 그 사이의 세 변이 같은 색인지 검사합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from itertools import combinations

def check_all(n):
    edges = list(combinations(range(n), 2))
    edge_index = {edge: i for i, edge in enumerate(edges)}
    triples = [
        [edge_index[e] for e in combinations(vertices, 2)]
        for vertices in combinations(range(n), 3)
    ]
    total = 1 << len(edges)
    without_triangle = 0
    minimum = len(triples)

    for coloring in range(total):
        count = 0
        for i, j, k in triples:
            if ((coloring >> i) & 1) == ((coloring >> j) & 1) == ((coloring >> k) & 1):
                count += 1
        without_triangle += (count == 0)
        minimum = min(minimum, count)

    return total, without_triangle, minimum

for n in range(3, 7):
    total, missing, minimum = check_all(n)
    print(f"{n}명: 전체 {total}가지, 삼각형 없음 {missing}가지, 최소 {minimum}개")

1
2
3
4
3명: 전체 8가지, 삼각형 없음 6가지, 최소 0개
4명: 전체 64가지, 삼각형 없음 18가지, 최소 0개
5명: 전체 1024가지, 삼각형 없음 12가지, 최소 0개
6명: 전체 32768가지, 삼각형 없음 0가지, 최소 2개

6명일 때의 ‘최소 2개’는 최초의 증명보다 조금 더 강력한 발견입니다. 실제로 각 꼭짓점에서 빨간색 변의 수를 $r_v$, 파란색 변의 수를 $b_v$ 라고 하면, $r_v+b_v=5$ 이고 $r_vb_v\leq6$ 입니다.

단색이 아닌 삼각형에는 빨간색과 파란색 두 변이 만나는 꼭짓점이 정확히 2개 존재합니다. 따라서 각 꼭짓점에서 ‘빨간 변 1개·파란 변 1개 쌍’을 세면, 단색이 아닌 삼각형을 2번씩 세게 됩니다. 전체 삼각형은 20개이므로,

$$ T=\binom63-\frac12\sum_{v=1}^{6}r_vb_v \geq20-\frac12\cdot6\cdot6=2 $$

로 증명할 수 있습니다. 게다가 6개의 꼭짓점을 3개씩 두 그룹으로 나누고, 각 그룹 내부는 빨간색, 그룹 사이를 연결하는 변은 파란색으로 칠하면 빨간색 삼각형이 2개, 파란색 삼각형이 0개가 됩니다. 따라서 최솟값 2 또한 정확합니다.

이러한 전수 열거는 작은 인원수에는 효과적이지만, 색칠의 총 가짓수는 $2^{n(n-1)/2}$ 로 급증합니다. 인원수를 늘려 동일한 코드를 실행하면 순식간에 과부하가 걸리므로 여기서는 3~6명으로 한정했습니다. 그림과 상세한 분포는 재현용 스크립트와 계산 결과 JSON에서 확인할 수 있습니다.

8. 응용 ①: 네트워크의 ‘완전 연결’ 또는 ‘완전 비연결’

‘아는 사이’라는 말을 장치 간의 ‘직접 연결’로 바꾸어 봅시다. 6대의 장치가 있고 각 쌍은 ‘직접 연결됨’ 또는 ‘직접 연결되지 않음’ 둘 중 하나라고 가정합니다. 방향성이 없는 연결이라면 동일한 정리를 그대로 적용할 수 있습니다.

그러면 3대의 모든 쌍 사이에 연결이 존재하는 그룹이나, 3대의 어느 쌍 사이에도 직접 연결이 없는 그룹이 반드시 존재합니다. 전자는 꼭짓점 3개의 클리크 , 후자는 꼭짓점 3개의 독립 집합 입니다. 여기서 ‘직접 연결되지 않음’은 다른 장치를 경유해서도 통신할 수 없다는 뜻은 아닙니다.

이러한 관점은 쌍별로 양립 여부를 결정한 작업 스케줄링이나 상호관계를 조사하는 소규모 네트워크의 설계 검증에도 활용할 수 있습니다. “모든 쌍이 양립하는 3건도, 모든 쌍이 양립하지 않는 3건도 모두 피하고 싶다"고 요구하더라도 대상이 6건이라면 탐색하기 전부터 불가능하다는 것을 알 수 있습니다.

다만 정리는 둘 중 어느 쪽이 나타날지를 선택해주지는 않습니다. 양립하는 3건을 원했는데 양립하지 않는 3건만 발견될 수도 있습니다. 또한 쌍 단위로는 양립하더라도 3건이 동시에 실행되기에는 자원이 부족하다는 식의 조건은 별도로 확인해야 합니다. 보장의 대상은 어디까지나 주어진 이항 관계입니다.

9. 응용 ②: 뒤섞인 수열에서 증가·감소 수열 추출하기

서로 다른 6개의 수를 순서대로 나열합니다. 위치 $i$ 가 $j$ 보다 앞서 있을 때, $a_i\lt a_j$ 이면 빨간색, $a_i\gt a_j$ 이면 파란색으로 두 위치를 연결합니다.

이 역시 꼭짓점 6개인 완전 그래프의 2색 색칠입니다. 따라서 단색 삼각형이 존재합니다. 그 3개의 위치를 작은 순서대로 $i\lt j\lt k$ 라고 하면, 빨간색 삼각형의 경우 다음과 같습니다.

$$ a_i\lt a_j\lt a_k $$

파란색 삼각형의 경우 다음과 같습니다.

$$ a_i\gt a_j\gt a_k $$

즉, 원래 순서를 유지한 채로 증가하는 3개 항이나 감소하는 3개 항을 반드시 추출할 수 있다 는 것을 알 수 있습니다. 꼭 연속되어 있을 필요는 없습니다. 이처럼 순서를 바꾸지 않고 일부를 뽑아낸 것을 부분수열이라고 부릅니다.

수열 4, 1, 5, 2, 6, 3에서 원래 위치 2, 4, 6을 선택하여 증가 부분수열 1, 2, 3을 추출하는 그림

그림의 수열 $4,1,5,2,6,3$ 에서는 2번째, 4번째, 6번째 수를 선택하면 $1,2,3$ 을 얻을 수 있습니다. 숫자를 크기순으로 재배열한 것이 아니라 원래의 출현 순서를 유지하면서 선택한 것입니다.

이는 데이터 열 안에서 규칙적인 부분 구조를 찾아내는 사고방식으로 이어집니다. 다만 골라낸 3개 항이 증가하고 있다고 해서 데이터 전체가 상승 추세에 있다는 증거가 되지는 않습니다. 어떤 배열에서든 반드시 나타나는 형태라면, 그것이 존재한다는 사실만으로는 특별한 현상이라고 볼 수 없기 때문입니다.

참고로 이 수열 문제에서는 반드시 6개 항이 필요한 것은 아니며, 실제로는 서로 다른 5개 항만으로도 길이 3의 증가 또는 감소 부분수열이 보장됩니다. 이것은 에르되시-세케레시(Erdős–Szekeres) 단조 부분수열 정리의 특수한 경우입니다. 수열로 만드는 색칠에는 대소 관계에 따른 제약이 존재하기 때문에, 임의의 2색 색칠보다 더 강력한 결과를 얻을 수 있습니다. 단조 부분수열에 관한 강의 자료

10. 정리: 무질서 속에도 피할 수 없는 형태가 있다

6명의 관계를 빨간색과 파란색으로 변환하고 한 사람에게서 나오는 5개의 선에 주목하는 것만으로 단색 삼각형이 반드시 존재함을 증명할 수 있었습니다. 5명의 오각형 배치는 반례를 제공하므로 램지 수는 $R(3,3)=6$ 입니다.

기억해 두어야 할 점은 다음 세 가지입니다.

‘반드시’는 무작위 실험에서 확률이 높다는 뜻이 아니다. 5명에서는 약 98.83%라도 반례가 남고, 6명에서는 단 하나도 남지 않습니다.
규칙의 존재와 그 규칙의 의미는 별개이다. 단색 삼각형이나 증가 부분수열이 존재한다는 사실만으로 집단 전체의 성질이나 인과관계가 결정되지는 않습니다.
보장에는 대상과 조건이 따른다. 관계가 대칭인지, 모든 쌍을 2가지로 분류할 수 있는지, 어떤 부분 구조를 찾을 것인지를 명확히 해야 합니다.

램지 이론의 묘미는 복잡한 전체가 단순해지는 데 있지 않습니다. 전체는 복잡한 채로 남아 있더라도 그 안의 작은 규칙을 완전히 지워버릴 수는 없습니다. 종이 위에 그린 몇 개의 선으로부터 이 깊이 있는 사고방식을 확인할 수 있습니다.

참고 자료

Ohio State University, Ramsey Theory: 변의 2색 색칠과 작은 램지 수에 대한 해설.
Yuval Wigderson, PCMI 2025, Extremal graph theory and Ramsey theory: Lecture 10: 단조 부분수열을 포함한 램지적 사고방식에 대한 강의 자료.

본 기사의 그림, 전수 조사 표, 확률 및 개수 분포는 첨부된 Python 스크립트로 생성되었습니다.