에르되시-세케레시 정리

1. 개요

에르되시-세케레시 정리는 임의의 수열 내에서 증가하거나 감소하는 부분 수열의 최소 길이에 대한 정리이다. 이 정리는 기하학적 해석, 순열 패턴 해석, 비둘기집 원리, 딜워스 정리, 로빈슨-시엔셰드 대응 등을 통해 증명될 수 있다. 특히, 길이가 (r-1)(s-1)+1인 모든 순열은 길이 r의 증가하는 부분 수열 또는 길이 s의 감소하는 부분 수열을 갖는다는 것을 보장한다.

2. 예시

r = 3, s = 2인 경우, 에르되시-세케레시 정리에 따르면 세 숫자의 임의 순열은 길이 3의 증가하는 부분 수열 또는 길이 2의 감소하는 부분 수열을 갖는다. 예를 들어, 숫자 1, 2, 3의 순열에 대해 다음과 같은 경우가 있다.

* 1, 2, 3은 세 숫자 모두로 구성된 증가하는 부분 수열을 갖는다.
* 1, 3, 2는 감소하는 부분 수열 3, 2를 갖는다.
* 2, 1, 3은 감소하는 부분 수열 2, 1을 갖는다.
* 2, 3, 1은 두 개의 감소하는 부분 수열 2, 1과 3, 1을 갖는다.
* 3, 1, 2는 두 개의 감소하는 부분 수열 3, 1과 3, 2를 갖는다.
* 3, 2, 1은 세 개의 감소하는 부분 수열 3, 2, 3, 1, 2, 1을 갖는다.

3.

4. 다른 해석

4.1. 기하학적 해석

수열에 있는 수의 위치를 유클리드 평면에 있는 점의 x 좌표로 해석하고 수 자체를 y 좌표로 해석할 수 있다. 반대로 평면에 있는 모든 점에 대해 두 점이 동일한 x 좌표를 갖지 않는 한 x 좌표로 정렬된 점의 y 좌표는 수열을 형성한다. 수열과 점 집합 사이의 이러한 변환으로 에르되시-세케레시 정리는 다음과 같이 해석될 수 있다: 적어도 점 $rs-r-s+2$개를 갖는 모든 집합에서 양의 기울기 모서리 $r-1$개 또는 음의 기울기 모서리 $s-1$개로 이루어진 다각형 경로를 찾을 수 있다. 특히 $r=s$인 경우 최소한 $n$개의 점 집합에서 동일한 부호 기울기를 가진 최소한 $\backslash left\backslash lfloor\; \backslash sqrt\{n\; -\; 1\}\; \backslash right\backslash rfloor$개의 모서리를 갖는 다각형 경로를 찾을 수 있다. 예를 들어 $r=s=5$ 을 취하면 17개 이상의 점으로 구성된 모든 집합은 모든 기울기가 동일한 부호를 갖는 모서리 4개의 경로를 갖는다.

$(r-1)\; \backslash times\; (s-1)$ 격자를 약간 회전시켜 이러한 경로가 포함하지 않는 점 $rs\; -\; r\; -\; s\; +\; 1$개의 집합을 구성할 수 있고, 이는 이 경계가 정확하다는 것을 보여준다.

4.2. 순열 패턴 해석

에르되시-세케레시 정리는 길이가 최소 (r - 1)(s - 1) + 1인 모든 순열 패턴이 패턴 12⋯r 또는 패턴 s⋯21을 포함해야 한다는 순열 패턴의 언어로 해석될 수 있다.

5. 증명

에르되시-세케레시 정리는 여러 가지 방법으로 증명할 수 있다. Steele (1995)은 에르되시-세케레시 정리의 여섯 가지 증명을 조사하였는데, 여기에는 에르되시와 세케레시의 원본 증명, Blackwell (1971), Hammersley (1972), Lovász (1979)의 증명이 포함된다.

5.1. 비둘기집 원리

길이 $(r-1)(s-1)+1$의 주어진 수열에 대해, 각 수 $n\_i$에 $(a\_i,\; b\_i)$ 쌍을 붙인다. 이때 $a\_i$는 $n\_i$로 끝나는 가장 긴 단조 증가 부분 수열의 길이이고, $b\_i$는 $n\_i$로 끝나는 가장 긴 단조 감소 부분 수열의 길이이다. 수열의 서로 다른 두 수는 다른 쌍이 붙는다. 즉,

$a\_i$가 $r$보다 작고 $b\_i$가 $s$보다 작은 쌍은 많아야 $(r-1)(s-1)$개 존재한다. 따라서 비둘기집 원리에 의해 $a\_i$ 또는 $b\_i$가 범위를 벗어나는 $i$값이 존재한다. $a\_i$가 범위를 벗어나면 $n\_i$는 길이 $r$ 이상인 증가 부분 수열의 일부이고, $b\_i$가 범위를 벗어나면 $n\_i$는 길이 $s$ 이상인 감소 부분 수열의 일부이다.

스틸은 Seidenberg (1959)의 한 쪽 짜리 논문을 그가 조사한 증명 중 "가장 매끄럽고 체계적인" 증명으로 인정했다.

5.2. 딜워스 정리

에르되시-세케레시 정리의 또 다른 증명은 부분 순서 집합에서 체인 분해에 관한 딜워스 정리 또는 이의 더 간단한 쌍대 정리인 미르스키 정리를 사용한다.

이 정리를 증명하기 위해 수열의 멤버에 부분 순서를 정의하는데, 여기서 부분 순서에서 x는 숫자로서 x ≤ y이고, 수열에서 x가 y보다 앞선다면 y보다 작거나 같다. 이 부분 순서에서 체인은 단조 증가하는 부분 수열이고, 안티체인은 단조 감소하는 부분 수열이다. 미르스키 정리에 의해, 길이가 r인 체인이 있거나, 수열이 최대 r − 1개의 안티체인으로 분할될 수 있는데, 이 경우 안티체인 중 가장 큰 것이 길이가 최소한
:$\backslash left\backslash lceil\backslash frac\{rs-r-s+2\}\{r-1\}\backslash right\backslash rceil=s.$
인 감소하는 부분 수열을 형성한다.

또는, 딜워스 정리 자체에 의해 길이가 s인 안티체인이 있거나, 수열이 최대 s − 1개의 체인으로 분할될 수 있으며, 이 중 가장 긴 것은 길이가 최소한 r이어야 한다.

5.3. 로빈슨-시엔셰드 대응

이 결과는 로빈슨-시엔셰드 대응의 따름정리로 얻을 수 있다.

로빈슨-시엔셰드 대응은 각 수열에 수열의 값을 항목으로 갖는 영 도표 P를 대응시킨다는 것을 기억하자. 도표 P는 다음과 같은 성질을 갖는다.

* 최장 증가 부분 수열의 길이는 P의 첫 번째 행의 길이와 같다.
* 최장 감소 부분 수열의 길이는 P의 첫 번째 열의 길이와 같다.

(r − 1)(s − 1) 크기의 정사각형 상자에 (r − 1)(s − 1) + 1 개의 항목을 넣는 것은 불가능하므로, 첫 번째 행의 길이가 최소 r이거나 마지막 열의 길이가 최소 s이다.