azberjibiou's profile image

azberjibiou

December 25, 2025 00:00

서론

Extremal Graph Theory의 핵심 질문은 “무질서해 보이는 구조가 충분히 크다면, 그 안에 특정한 패턴이 필연적으로 존재하는가?”이다.

본 글에서는 이러한 ‘필연적 질서’에 대한 논의를 1차원 수열에서 시작하여 2차원 기하 영역으로 확장한다. 구체적으로 Erdős-Szekeres Theorem을 통해 수열에서의 단조 부분 수열의 존재성을 증명하고, 이를 일반화하여 평면 기하학의 난제 중 하나였던 Happy Ending Problem과 볼록 다각형의 존재성에 대한 상한과 하한을 논한다.

1. Erdős-Szekeres Theorem

Extremal Graph Theory의 논의를 시작하기 위해, 가장 기초적이면서도 강력한 정리를 소개한다. 이는 1차원 수열 데이터에서 길이가 충분히 길다면, 필연적으로 단조성이 발생함을 보장한다.

Theorem (Erdős-Szekeres). 서로 다른 실수로 이루어진 길이 $(k-1)(l-1) + 1$ 이상의 수열 $A$는 항상 다음 중 적어도 하나를 만족한다.

• 길이 $k$ 이상의 증가 부분 수열이 존재한다.
• 길이 $l$ 이상의 감소 부분 수열이 존재한다.

Proof. 귀류법과 비둘기집 원리를 사용하여 증명한다.

주어진 수열을 $A = {a_1, a_2, \dots, a_N}$이라 하고, $N = (k-1)(l-1) + 1$이라 하자. 결론을 부정하여, 수열 $A$가 길이 $k$ 이상의 증가 부분 수열도 없고, 길이 $l$ 이상의 감소 부분 수열도 없다고 가정한다.

각 원소 $a_i$에 대하여, $c_i$를 다음과 같이 정의한다.

$c_i$: $a_i$를 마지막 원소로 하는 최장 증가 부분 수열의 길이

가정에 의해 길이 $k$ 이상의 증가 부분 수열은 존재하지 않으므로, 모든 $i$에 대하여 $c_i$의 범위는 $1 \le c_i \le k-1$이다.

비둘기집 원리에 의해 어떤 정수 $x$ ($1 \le x < k$)에 대하여, $c_i = x$를 만족하는 인덱스가 $l$개 이상 존재한다. 이 인덱스들을 오름차순으로 $i_1 < i_2 < \dots < i_l$이라 하자.

이제 이 인덱스에 대응하는 원소들의 부분 수열 $a_{i_1}, a_{i_2}, \dots, a_{i_l}$을 살펴보자. 만약 어떤 $j$에 대해 $a_{i_j} < a_{i_{j+1}}$라면, $a_{i_j}$로 끝나는 증가 수열 뒤에 $a_{i_{j+1}}$을 붙여 길이를 늘릴 수 있다. 이 경우 $c_{i_{j+1}} \ge c_{i_j} + 1$이 되어야 하는데, 우리는 $c_{i_j} = c_{i_{j+1}} = x$라고 가정했으므로 이는 모순이다.

그러므로 모든 인접한 쌍에 대해 $a_{i_j} > a_{i_{j+1}}$가 성립해야 한다. \(a_{i_1} > a_{i_2} > \dots > a_{i_l}\) 이는 길이 $l$인 감소 부분 수열이 존재함을 의미한다.

최초 가정에 의해 길이 $l$인 감소 부분 수열 또한 없어야 하므로, 모순이 발생한다. 따라서 정리는 참이다. $\blacksquare$

참고로 위 정리가 제시하는 길이 $(k-1)(l-1)+1$은 최적이다. 즉, 길이가 $(k-1)(l-1)$이면서 조건을 만족하지 않는 수열을 항상 구성할 수 있다. 아래 그림은 $k=4, l=4$일 때, 길이 $(3-1)(4-1)=9$인 수열에서 길이 4의 증가/감소 부분 수열이 존재하지 않도록 배치한 예시이다.

2. 기하학적 확장: Convex Set과 Concave Set

수열에서의 단조성 개념을 2차원 평면으로 확장해보자.

Definition. 평면 위에 $x$좌표가 서로 다른 $N$개의 점이 주어졌다고 가정하자. 이 점들을 $x$좌표가 증가하는 순서대로 $P_1, P_2, \dots, P_N$이라 정렬한다. 인접한 두 점을 잇는 선분의 기울기를 $m_i$라 할 때, 점들의 집합에 대해 다음과 같은 구조를 정의한다.

• $s$-convex set: 연속된 선분들의 기울기가 단조 증가하는 $s$개의 점. ($m_1 < m_2 < \dots < m_{s-1}$)
• $t$-concave set: 연속된 선분들의 기울기가 단조 감소하는 $t$개의 점. ($m_1 > m_2 > \dots > m_{t-1}$)

함수 $R(s, t)$를 임의의 위치에 있는 점들 중에서 항상 $s$-convex set 혹은 $t$-concave set을 포함하도록 보장하는 점의 개수로 정의한다.

Lemma. 함수 $R(s, t)$는 다음의 점화식을 만족한다.

\[R(s, t) = R(s-1, t) + R(s, t-1) - 1\]

Proof. 점의 개수가 $N = R(s-1, t) + R(s, t-1) - 1$이라고 가정하자. 또한 집합 내에 $t$-concave set과 $s$-convex set이 모두 존재하지 않는다고 가정하자.

어떤 $(s-1)$-convex set의 끝점으로 한 번 이상 등장하는 점들의 집합을 $S$라고 하자. 만약 $S$에 포함되지 않는 점의 개수가 $R(s-1, t)$개 이상이라면, 정의에 의해 그 점들 사이에서 $(s-1)$-convex set을 찾을 수 있다. 이 경우 해당 Convex set의 마지막 점은 $S$에 포함되어야 하므로 모순이다. 따라서 $S$의 크기는 $R(s, t-1)$ 이상이어야 한다.

$R(s, t-1)$의 정의에 따라, $S$ 안에는 $s$-convex set 혹은 $(t-1)$-concave set이 존재해야 한다. 우리는 $s$-convex set이 없다고 가정했으므로, $S$ 내부에는 반드시 $(t-1)$-concave set이 존재한다.

이 $(t-1)$-concave set의 첫 번째 점을 $A_1$, 두 번째 점을 $A_2$라 하자. $A_1$은 $S$의 원소이므로, 어떤 $(s-1)$-convex set $C$의 마지막 점이었다. $C$의 끝에서 두 번째 점을 $B$라고 할 때, 선분 $BA_1$과 $A_1A_2$의 기울기를 비교한다.

1. $slope(BA_1) < slope(A_1A_2)$인 경우: 기울기가 증가하였으므로, $A_2$를 $C$ 뒤에 붙여 길이 $s$인 Convex set을 만들 수 있다.
2. $slope(BA_1) > slope(A_1A_2)$인 경우: 기울기가 감소하였으므로, $B$를 $A_1 \dots$ 수열 앞에 붙여 길이 $t$인 Concave set을 만들 수 있다.

####

어떤 경우든 가정에 모순이 발생한다. 따라서 $R(s, t)$개의 점이 있으면 조건을 만족하는 집합이 반드시 존재한다. $\blacksquare$

위 점화식을 풀면 아래와 같은 식을 얻어낼 수 있다.

\[R(s, t) = \binom{s+t-4}{s-2} + 1\]

3. 하한의 구성

앞서 우리는 $R(s, t) = \binom{s+t-4}{s-2} + 1$개의 점이 있으면 $s$-convex set 혹은 $t$-concave set이 반드시 존재함을 증명하였다. 이제 이 Bound가 Tight함을 보이기 위해, 정확히 $\binom{s+t-4}{s-2}$개의 점이 있을 때 해당 구조가 존재하지 않도록 하는 반례를 구성한다.

Theorem. 다음 조건을 만족하는 크기 $M = \binom{s+t-4}{s-2}$인 점 집합 $S$가 존재한다.

1. 길이 $s$의 Convex set을 포함하지 않는다.
2. 길이 $t$의 Concave set을 포함하지 않는다.

Construction. 우리는 $x$좌표가 $1$부터 $M$까지인 점들의 집합 $S = {(x, g(x)) \mid x = 1, \dots, M}$을 정의한다. 여기서 $y$좌표를 결정하는 함수 $g(x)$는 다음과 같이 재귀적으로 구성된다.

집합 $S$를 두 개의 부분 집합 $A$와 $B$로 분할한다.

• 집합 A (Left Part): 처음 $\binom{(s-1)+t-4}{(s-1)-2}$개의 점. 이는 $R(s-1, t)-1$에 해당한다.
• 집합 B (Right Part): 나머지 점들. 개수는 파스칼의 항등식에 의해 $\binom{s+(t-1)-4}{s-2}$개가 되며, 이는 $R(s, t-1)-1$에 해당한다.

이때 집합 $B$의 $y$좌표에 매우 큰 상수 $C$를 더하여 $A$의 모든 점보다 $B$의 모든 점이 월등히 높은 위치에 있도록 배치한다. 즉, $A$와 $B$를 잇는 선분의 기울기가 $A$ 내부의 어떤 기울기나 $B$ 내부의 어떤 기울기보다도 크도록 설정한다.

Proof. 이와 같이 구성된 집합 $S$에서 길이 $s$의 Convex set이나 길이 $t$의 Concave set이 존재하지 않음을 보인다.

길이 $s$의 convex set이 존재하지 않음을 보이자. 길이 $t$의 concave set이 존재하지 않음은 비슷하게 보일 수 있다. Convex set은 기울기가 단조 증가($m_1 < m_2 < \dots$)해야 한다. 만약 이 집합이 $A$와 $B$에 걸쳐 있다고 가정하자. $A$에서 $B$로 넘어가는 구간의 기울기 $m_{cross}$는 설정에 의해 매우 큰 양수이다. 반면, $B$ 내부에서의 기울기 $m_{B}$는 $m_{cross}$보다 작다 ($m_{cross} \gg m_{B}$). 따라서 기울기가 감소하게 되어 Convex 성질($m_{cross} < m_{B}$ 필요)이 깨진다. 그러므로 Convex set은 전적으로 $B$에 있거나 $B$와의 교집합 크기가 $1$ 이하이다. 귀납 가정에 의해 $A$는 $(s-1)$-convex set을 가질 수 없고 (최대 길이 $s-2$), $B$는 $s$-convex set을 가질 수 없다. 따라서 전체 집합 $S$는 $s$-convex set을 가지지 않는다.

결론적으로, 이 구성은 $R(s, t)$의 상한 공식이 최적임을 보여준다.

4. $n$-convex polygon이 없는 $2^{n-2}$개의 점

$n$-convex polygon을 포함하지 않는 $2^{n-2}$개의 점의 존재성에 대해서 보이자.

Construction. 우리는 볼록 $n$각형을 포함하지 않는 $2^{n-2}$개의 점들의 집합 $S$를 구성하고자 한다. 앞서 3장에서 보인 내용에 따라 $S_{k, l}$을 길이 $k$의 Concave set과 길이 $l$의 Convex set이 없는 길이 $\binom{k+l-4}{l-2}$의 집합으로 정의하자.

집합 $S$를 다음과 같이 $n-1$개의 부분 집합 $T_k$ ($k=1, \dots, n-1$)의 합집합으로 정의한다. 여기서 각 $T_k$는 $S_{k+1, n-k+1}$의 평행이동이다. 즉, $T_k$ 내부에는 길이 $k+1$의 Concave set이나 길이 $n-k+1$의 Convex set이 존재하지 않는다. $S$의 크기는 $\sum_{k=1}^{n-1} \binom{n-2}{k-1} = 2^{n-2}$이다.

$T_k$들은 평면 상에서 서로 멀리 떨어져 있으며, $k$가 증가할수록 $x$좌표가 커지고 $y$좌표는 급격히 작아지도록 배치된다. 구체적으로, 서로 다른 집합 $T_i, T_j$ ($i < j$)를 잇는 선분의 기울기는 음수이며, 그 절댓값은 매우 작거나 매우 크도록 조정되어 집합 간의 기울기 관계가 집합 내부의 기울기(양수)와 확연히 구분되도록 한다. $S_{i, j}$ 내부의 점들은 단조증가한다는 것이 중요하게 작용한다.

Proof. 구성된 집합 $S$에서 볼록 $n$각형이 존재하지 않음을 귀류법으로 증명한다. 만약 $S$의 부분집합 $P$가 볼록 $n$각형을 이룬다고 가정하자. $P$는 여러 $T_k$들에 걸쳐 있을 수 있다. $P$가 포함된 $T_k$들의 인덱스를 오름차순으로 $k_1 < k_2 < \dots < k_r$이라 하자.

볼록 다각형 $P$의 구성 원소는 다음과 같은 제한을 받는다.

1. 중간 집합 ($1 < i < r$): $P$가 $T_{k_i}$를 지나갈 때, 그 내부에서 2개 이상의 점을 선택할 수 없다. 만약 2개를 선택한다면 양수 기울기가 발생하여, 이전/이후의 음수 기울기와 결합될 때 볼록성(기울기 단조 감소)을 위배하게 된다. 따라서 중간 그룹에서는 최대 1개의 점만 선택 가능하다.
2. 첫 번째 집합 ($T_{k_1}$): 여기서 선택된 점들은 $P$의 시작 부분이므로, $T_{k_2}$로 넘어가는 음수 기울기와 연결되기 위해 내부적으로 기울기가 감소하는 형태, 즉 concave sequence를 이뤄야 한다. $T_{k_1}$의 속성에 의해 최대 길이는 $k_1$이다.
3. 마지막 집합 ($T_{k_r}$): 여기서 선택된 점들은 $P$의 끝 부분이므로, $T_{k_{r-1}}$에서 오는 음수 기울기를 받아 내부적으로 Convex sequence를 이뤄야 한다. $T_{k_r}$의 속성에 의해 최대 길이는 $n-k_r$이다.

따라서 $

P

\leq k_1 + (r-2) + n-k_r \le k_1 + (k_r - k_1 - 1) + n-k_r = n-1$이다.

결과적으로 볼록 $n$각형은 존재하지 않는다. $\blacksquare$

5. 결론 및 미해결 과제

본 글에서는 Erdős-Szekeres Theorem을 시작으로, 1차원 수열의 단조성이 2차원 기하학적 구조로 확장되는 과정을 살펴보았다. 우리는 점들의 집합이 충분히 커지면 그 안에 필연적으로 볼록 다각형이 발생함을 증명하였다.

우리가 도출한 상한 $R(n, n) = \binom{2n-4}{n-2}+1$과 구성적 하한 $2^{n-2}+1$ 사이에는 여전히 간극이 존재한다. 하지만 학계의 정설은 정답이 하한 쪽에 있을 것이라는 추측으로 모아지고 있다.

Erdős-Szekeres Conjecture 일반 위치에 있는 점들의 집합에서 볼록 $n$각형을 보장하는 최소의 점 개수 $N(n)$은 $2^{n-2} + 1$이다.

이 추측은 작은 $n$에 대하여 이미 참임이 확인되었다.

• $n=3$: $N(3) = 2^1 + 1 = 3$ (삼각형은 점 3개로 항상 존재)
• $n=4$: $N(4) = 2^2 + 1 = 5$ (점 5개면 볼록 사각형 존재 - E. Klein)
• $n=5$: $N(5) = 2^3 + 1 = 9$ (점 9개면 볼록 오각형 존재 - E. Makai)

$n=6$인 경우 $N(6)=17$임이 컴퓨터를 이용한 증명으로 밝혀졌으나(Szekeres & Peters, 2006), 일반적인 $n$에 대한 등식은 아직 증명되지 않은 난제로 남아 있다. 최근 Andrew Suk(2017)에 의해 상한이 $2^{n + o(n)}$ 수준까지 획기적으로 개선되었으나, 정확한 값의 증명은 여전히 요원하다.