맨위로가기

에르되시-세케레시 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

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

더 읽어볼만한 페이지

  • 이산수학 정리 - 애로의 불가능성 정리
    애로의 불가능성 정리는 3개 이상의 선택지에서 약한 파레토, 무관한 대안으로부터의 독립성, 비독재성을 모두 만족하는 사회 후생 함수는 존재하지 않음을 증명한 정리이다.
  • 이산수학 정리 - 비둘기집 원리
    비둘기집 원리는 n개의 비둘기집에 n+1마리 이상의 비둘기를 넣으면 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어간다는 간단한 원리이며, 귀류법으로 증명되고, 소프트볼 팀 구성, 해시 테이블 충돌 등 다양한 분야에 응용된다.
  • 이산기하학 정리 - 헬리의 정리
    헬리의 정리는 d차원 공간의 볼록 부분집합들 중 임의의 d+1개의 교집합이 공집합이 아니면 전체 집합의 교집합도 공집합이 아니라는 정리이다.
  • 이산기하학 정리 - 라돈의 정리
    d차원 공간에서 d+2개의 점으로 이루어진 집합은 볼록 껍질이 교차하는 두 개의 부분집합으로 분할할 수 있다는 라돈의 정리는 헬리의 정리 증명에 사용될 뿐 아니라 VC 차원 계산과 중심점 근사 알고리즘 등 다양한 분야에 응용된다.
  • 램지 이론 - 램지의 정리
    램지의 정리는 주어진 조건을 만족하는 램지 수가 존재한다는 정리로, 그래프 이론으로 해석되며, 특정 크기의 동색 클릭이 존재함을 보장하고, 램지 이론의 시초로 여겨진다.
  • 램지 이론 - 비둘기집 원리
    비둘기집 원리는 n개의 비둘기집에 n+1마리 이상의 비둘기를 넣으면 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어간다는 간단한 원리이며, 귀류법으로 증명되고, 소프트볼 팀 구성, 해시 테이블 충돌 등 다양한 분야에 응용된다.
에르되시-세케레시 정리
정리 정보
이름에르되시-세케레시 정리
분야조합론
설명임의의 수열에서 단조 부분수열의 존재성을 보장하는 정리
내용충분히 긴 수열은 긴 단조 부분수열을 가진다.
증명비둘기집 원리를 사용하여 증명 가능
관련 인물파울 에르되시, 조지 세케레시
발표 연도1935년
중요성램지 이론의 초기 결과 중 하나
응용다양한 조합론적 문제 해결에 활용
일반화더 일반적인 조건 하에서 단조 부분수열의 존재성을 보장하는 정리로 확장 가능

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. 다른 해석

3. 1. 기하학적 해석

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

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

3. 2. 순열 패턴 해석

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

4. 증명

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

4. 1. 비둘기집 원리

길이 (r-1)(s-1)+1의 주어진 수열에 대해, 각 수 n_i에 (a_i, b_i) 쌍을 붙인다. 이때 a_i는 n_i로 끝나는 가장 긴 단조 증가 부분 수열의 길이이고, b_i는 n_i로 끝나는 가장 긴 단조 감소 부분 수열의 길이이다. 수열의 서로 다른 두 수는 다른 쌍이 붙는다. 즉, i이고 n_i \le n_j이면 a_i < a_j이고, n_i \ge n_j이면 b_i < b_j이다.

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)의 한 쪽 짜리 논문을 그가 조사한 증명 중 "가장 매끄럽고 체계적인" 증명으로 인정했다.[11][12][2][6]

4. 2. 딜워스 정리

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

이 정리를 증명하기 위해 수열의 멤버에 부분 순서를 정의하는데, 여기서 부분 순서에서 ''x''는 숫자로서 ''x'' ≤ ''y''이고, 수열에서 ''x''가 ''y''보다 앞선다면 ''y''보다 작거나 같다. 이 부분 순서에서 체인은 단조 증가하는 부분 수열이고, 안티체인은 단조 감소하는 부분 수열이다. 미르스키 정리에 의해, 길이가 ''r''인 체인이 있거나, 수열이 최대 ''r'' − 1개의 안티체인으로 분할될 수 있는데, 이 경우 안티체인 중 가장 큰 것이 길이가 최소한

:\left\lceil\frac{rs-r-s+2}{r-1}\right\rceil=s.

인 감소하는 부분 수열을 형성한다.

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

4. 3. 로빈슨-시엔셰드 대응

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

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

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


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

참조

[1] 간행물 A combinatorial problem in geometry http://www.numdam.or[...]
[2] 간행물 Discrete Probability and Algorithms http://www-stat.whar[...] Springer-Verlag
[3] 간행물 An alternative proof of a theorem of Erdős and Szekeres
[4] 간행물 Proc. 6th Berkeley Symp. Math. Stat. Prob. University of California Press
[5] 간행물 Combinatorial Problems and Exercises North-Holland
[6] 간행물 A simple proof of a theorem of Erdős and Szekeres
[7] 간행물 http://www.numdam.or[...]
[8] 간행물 http://www-stat.whar[...] Springer-Verlag
[9] 간행물 University of California Press
[10] 간행물 North-Holland
[11] 간행물 Discrete Probability and Algorithms http://www-stat.whar[...] Springer-Verlag
[12] 간행물 A simple proof of a theorem of Erdős and Szekeres http://jlms.oxfordjo[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com