[조합론] Erdős–Szekeres Theorem

0. 필요한 배경지식

 

 - 가장 긴 단조증가하는 부분수열

 - 비둘기집의 원리(pigeonhole principle)

 

 

1. 서론

 

가장 긴 단조증가하는 부분수열(LIS)를 찾는 문제는 이산수학에서 유명한 문제로, 길이 N인 수열의 LIS의 길이를 구하는 문제나 그런 길이의 단조증가 부분수열을 직접 찾는 문제는 모두 O(NlogN)에 해결할 수 있다.

심지어는 길이가 N인 수열의 서로 다른 LIS가 몇 개 존재하는지 찾는 문제 또한 O(NlogN)에 해결할 수 있다.

 

LIS를 구하다보면 LIS가 전체 수열의 길이에 비해 특히 짧은 경우들을 자주 만날 수 있다.

이런 경우를 만나면 LIS와 반대방향인, 가장 긴 단조감소하는 부분수열(이후 LDS라 칭한다)의 길이가 길어지는 것이 자주 눈에 띄지 않는가?

 

Erdős–Szekeres Theorem은 이러한 관점에서 바라볼 때, 주어진 모든 원소가 서로 다른(distinct) 수열이 주어졌을 때 LIS의 길이와 LDS의 길이 사이의 상관관계를 보여주는 정리이다.

 

 

2. 정리 소개

 

Erdős–Szekeres theorem는 다음과 같이 서술할 수 있다.

 

두 수 r과 s에 대하여, 모든 원소가 서로 다른(distinct) 길이가 rs + 1인 수열은

길이 r + 1인 LIS를 포함하거나 길이 s + 1인 LDS를 포함한다.

 

rs + 1보다 더 긴 길이의 수열은 길이가 rs + 1인 부분수열을 포함하므로 위의 성질을 만족한다.

 

증명을 하기 전에, 길이가 (r - 1)(s - 1)인 수열중에서 길이가 r + 1인 단조증가 부분수열과 길이가 s + 1인 단조감소 부분수열이 둘 다 존재하지 않는 예시를 직접 찾아보자. 아래 접은 글로 그러한 수열의 예시를 적어두었다.

다음과 같은 수열은 길이가 rs이지만 LIS의 길이가 r이고 LDS의 길이가 s이다.

s, s-1, s-2, ..., 2, 1, 2s, 2s-1, 2s-2, ..., s+2, s+1, 3s, 3s-1, ..., rs, rs-1, rs-2, ..., (r-1)s+2, (r-1)s+1

 

 

3. 증명

 

이 글에서는 Seidenberg의 증명을 소개한다.

 

길이가 rs + 1이고 모든 원소가 서로 다른 임의의 수열 a_i를 생각하자.

또한, m_i를 a_i서부터 시작되는 부분수열의 LIS의 길이, n_i를 a_i서부터 시작되는 부분수열의 LDS의 길이로 정의하자.

 

임의의 i < j에 대하여, 다음이 성립한다는 것을 쉽게 관찰할 수 있다.

 - a_i < a_j 이면 m_i > m_j 이다.

 - 반대로 a_i > a_j 이면 n_i > n_j 이다.

 

따라서, 각 i에 순서쌍 (m_i, n_i)를 대응시키면, 수열 a_i는 길이가 rs + 1이므로 서로 다른 rs + 1개의 순서쌍 (m_i, n_i)를 얻을 수 있다.

 

만약 a_i의 LIS의 길이가 r이고 LDS의 길이가 s이면, 만들 수 있는 서로 다른 순서쌍 (m_i, n_i)의 개수는 많아야 rs개이다.

따라서, 수열의 항이 rs개보다 많으므로, 비둘기집의 원리에 의해 이는 모순임을 알 수 있다.

 

따라서, LIS의 길이가 r보다 크거나, LDS의 길이가 s보다 클 수밖에 없음을 알 수 있다.

이것으로 Erdős–Szekeres Theorem이 증명되었다.

 

 

4. 응용

 

Erdős–Szekeres Theorem을 기하학적으로 생각해보자.

 

위 증명에서의 수열의 각 항 a_i를 2차원 좌표평면 위의 점 (i, a_i)에 대응시켜 생각을 해보면, Erdős–Szekeres theorem은 좌표평면 위의, 같은 x좌표 또는 y좌표를 가지지 않는 rs + 1개의 점에서 기울기가 연속적으로 양수인 r + 1개의 점 또는 기울기가 연속적으로 음수인 s + 1개의 점을 항상 찾을 수 있다는 것을 말해준다.

 

 

5. 여담

 

글쓴이는 다음 문제를 풀고 관련된 내용을 찾아보다가 위의 내용을 정리하게 되었다.

관심이 있다면 다음 문제를 풀어보자.

www.acmicpc.net/problem/1201

1201번: NMK

 

 

6. 참고한 내용

위키백과 Erdős–Szekeres Theorem: en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem

Seidenberg, A. (1959), "A simple proof of a theorem of Erdős and Szekeres"