맨위로가기

딜워스의 정리

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

1. 개요

딜워스의 정리는 부분 순서 집합의 너비와 사슬 분할의 최소 크기 간의 관계를 설명하는 정리이다. 딜워스의 정리에 따르면, 유한한 너비를 갖는 부분 순서 집합은 너비와 같은 수의 사슬로 분할될 수 있다. 미르스키의 정리는 딜워스 정리의 쌍대 명제로, 부분 순서 집합의 높이가 유한하면 높이와 같은 크기의 반사슬 분할이 존재한다는 것을 말한다. 딜워스의 정리는 쾨니그의 정리, 홀의 결혼 정리와 동치 관계에 있으며, 그래프 이론, 조합론 등 다양한 분야에 응용된다.

2. 정의

부분 순서 집합 (P,\le)의 '''높이'''(height영어)는 P 속의 사슬(부분 전순서 집합)의 크기의 상한이다. 즉, 다음과 같다.

:\operatorname{height}P=\sup\left\{n\colon x_1<\cdots

부분 순서 집합 (P,\le)의 '''너비'''(width영어)는 P 속의 반사슬의 크기의 상한이다. 즉, 다음과 같다.

:\operatorname{width}P=\sup\left\

3. 증명

미르스키의 정리는 딜워스의 정리보다 증명이 더 간단하며, 최대 사슬을 이용하여 증명할 수 있다.[2][3]

딜워스의 정리는 쾨니그의 정리를 통해 증명할 수 있으며, 이분 그래프 매칭 및 홀의 결혼 정리를 포함한 여러 다른 관련 정리와 동치이다.

딜워스 정리를 쾨니그의 정리를 사용하여 증명하는 방법은 다음과 같다. ''n''개의 원소를 가진 부분 순서 ''S''에 대해, 이분 그래프 ''G'' = (''U'',''V'',''E'')를 정의한다. 여기서 ''U'' = ''V'' = ''S''이고, ''S''에서 ''u'' < ''v''일 때 ''G''에 간선 (''u'',''v'')가 존재한다. 쾨니그의 정리에 의해, ''G''에는 매칭 ''M''과 정점 집합 ''C''가 존재하며, 각 간선은 ''C''에 최소한 하나의 정점을 포함하고 ''M''과 ''C''는 동일한 기수 ''m''을 갖는다. ''A''를 ''C''의 어떤 정점에도 해당하지 않는 ''S''의 원소 집합이라고 하면, ''A''는 최소 ''n'' - ''m''개의 원소를 갖고 (''C''가 이분 그래프의 양쪽에 동일한 원소에 해당하는 정점을 포함하는 경우 더 많을 수 있음) ''A''의 두 원소는 서로 비교할 수 없다. ''M''에 간선 (''x'',''y'')가 있을 때마다 ''x''와 ''y''를 동일한 체인에 포함하여 체인 집합 ''P''를 형성하면, ''P''는 ''n'' - ''m''개의 체인을 갖는다. 따라서 동일한 기수를 갖는 반사슬과 체인 분할을 구성할 수 있다.

딜워스 정리의 쾨니그 정리를 통한 증명: 부분 순서에서 이분 그래프를 구성하고 매칭에 따라 체인으로 분할


쾨니그의 정리를 딜워스 정리를 사용하여 증명하기 위해, 이분 그래프 ''G'' = (''U'',''V'',''E'')의 정점에 대한 부분 순서를 형성한다. ''u''가 ''U''에 있고 ''v''가 ''V''에 있으며, ''E''에 ''u''에서 ''v''로의 간선이 존재할 때 ''u'' < ''v''이다. 딜워스 정리에 의해, 동일한 크기를 갖는 반사슬 ''A''와 체인 분할 ''P''가 존재한다. 부분 순서에서 유일한 비자명 체인은 그래프의 간선에 해당하는 원소 쌍이므로, ''P''의 비자명 체인은 그래프에서 매칭을 형성한다. ''A''의 여집합은 이 매칭과 동일한 기수를 갖는 ''G''의 정점 덮개를 형성한다.

이분 매칭과의 연결을 통해 모든 부분 순서의 너비를 다항 시간에 계산할 수 있다. 너비 ''k''의 ''n''-원소 부분 순서는 시간 ''O''(''kn''2)에 인식될 수 있다.

3. 1. 딜워스의 정리 증명

쾨니그의 정리를 이용한 기법 등 딜워스의 정리 증명은 여러 방법이 있다.[2][3] 만약 P가 유한 집합일 경우, 미카 아셰르 페를레스(מִיכָה אָשֵׁר פרלסhe, 1936~)는 다음과 같은 간단한 증명을 제시하였다.

유한 부분 순서 집합 (P,\le)가 주어졌다고 하자. P의 극대 원소들의 집합을 \operatorname{max\,elem}(P), 극소 원소들의 집합을 \operatorname{min\,elem}(P)라고 하자. 이들은 각각 반사슬을 이룬다.

집합의 크기에 대한 수학적 귀납법을 사용하자. 우선, 딜워스의 정리는 한원소 집합인 부분 순서 집합에 대하여 자명하게 성립한다. 이제 딜워스의 정리가 크기 |P| 미만의 모든 부분 순서 집합에 대하여 성립한다고 가정하자. 그렇다면, 다음과 같이 두 가지 경우로 나눌 수 있다.

# 크기 \operatorname{width}P의 반사슬은 모두 \operatorname{max\,elem}(P)과 같거나, \operatorname{min\,elem}(P)와 같다.

# \operatorname{max\,elem}(P) 및 \operatorname{min\,elem}(P)와 같지 않은, 크기 \operatorname{width}P의 반사슬 A\subseteq P가 존재한다.

1의 경우, a\le b인 a\in\operatorname{min\,elem}(P)와 b\in\operatorname{max\,elem}(P)를 찾을 수 있다. (그렇지 아니하다면 크기가 \operatorname{width}P보다 더 큰 반사슬이 존재하게 되기 때문이다.) P\setminus\{a,b\}의 최소 사슬 분할

:P\setminus\{a,b\}=\bigsqcup_{i=1}^{c(P\setminus\{a,b\})}C_i

이 주어졌을 때

:P=\{a,b\}\sqcup \bigsqcup_{i=1}^{c(P\setminus\{a,b\})}C_i

는 P의 사슬 분할이므로, P\setminus\{a,b\}에 딜워스의 정리를 적용하면

:c(P)\le c(P\setminus\{a,b\})+1=\operatorname{width}(P\setminus\{a,b\})+1=\operatorname{width}P

이다.

2의 경우, 다음과 같은 두 부분 집합 A_\pm\subsetneq P를 정의하자.

:A_+=\{x\in P\colon\exists a\in A\colon x\ge a\}

:A_-=\{x\in P\colon\exists a\in A\colon x\le a\}

:\operatorname{width}(A_+)=\operatorname{width}(A_-)=|A|=\operatorname{width}P

:A_+\subsetneq P\supsetneq A_-

:A_+\cap A_-=A

A_\pm에 딜워스의 정리를 적용하여 다음과 같은 사슬 분해를 얻는다고 하자.

:A_\pm=\bigsqcup_{a\in A}C_\pm(a)

:\max C_-(a)=a=\min C_+(a)

그렇다면 P의 사슬 분해

:P=\bigsqcup_{a\in A}(C_+(a)\cup C_-(a))

를 얻는다. 즉,

:c(P)\le|A|=\operatorname{width}P

가 된다.

P 부분 순서 집합의 크기에 대한 귀납법을 이용한 다음 증명은 프레드 갤빈(Fred Galvin)의 증명을 기반으로 한다.

P를 유한 부분 순서 집합이라고 하자. P가 비어 있다면 정리는 자명하게 성립한다. 따라서 P에 적어도 하나의 원소가 있다고 가정하고, a를 P의 극대 원소라고 하자.

귀납법에 의해, 정수 k에 대해 부분 순서 집합 P':=P\setminus\{a\}가 k개의 서로소인 체인 C_1,\dots,C_k로 덮일 수 있고, 크기 k의 적어도 하나의 안티체인 A_0을 갖는다고 가정한다. 분명히 i=1,2,\dots,k에 대해 A_0\cap C_i\ne\emptyset이다. i=1,2,\dots,k에 대해, x_i를 P'에서 크기 k의 안티체인에 속하는 C_i의 극대 원소로 하고, A:=\{x_1,x_2,\dots,x_k\}로 설정한다.

A가 안티체인임을 보이자.

A_i를 x_i를 포함하는 크기 k의 안티체인이라고 하자. 임의의 서로 다른 인덱스 i와 j를 고정한다. 그러면 A_i\cap C_j\ne\emptyset이다. y\in A_i\cap C_j라고 하자. 그러면 x_j의 정의에 의해 y\le x_j이다. x_i\not \ge y이기 때문에 x_i\not \ge x_j이다. 이 논리에서 i와 j의 역할을 바꿔도 x_j\not\ge x_i이다. 따라서 A는 안티체인이다.

이제 P로 돌아가자. 먼저, i\in\{1,2,\dots,k\}에 대해 a\ge x_i라고 가정하자. K를 체인 \{a\}\cup\{z\in C_i:z\le x_i\}라고 하자. 그러면 x_i의 선택에 의해, P\setminus K는 크기 k의 안티체인을 갖지 않는다. A \setminus \{x_i \}가 P \setminus K에서 크기 k - 1의 안티체인이기 때문에 귀납법에 의해 P\setminus K는 k-1개의 서로소인 체인으로 덮일 수 있다.

따라서 P는 k개의 서로소인 체인으로 덮일 수 있다. 다음으로, 각 i\in\{1,2,\dots,k\}에 대해 a\not\ge x_i이면, A\cup\{a\}는 P에서 크기 k+1의 안티체인이다(a가 P에서 극대이므로). 이제 P는 k+1개의 체인 \{a\},C_1,C_2,\dots,C_k로 덮일 수 있으며, 증명이 완료된다.

3. 2. 미르스키의 정리 증명

부분 순서 집합 P가 유한한 높이를 가진다고 하자. 원소 x\in P에 대하여, N(x)를 x를 최대 원소로 하는 사슬의 길이의 최댓값이라고 하자. 이는 함수 N\colon P\to\mathbb N을 정의한다.

그렇다면, 각 자연수 n\in\mathbb N의 원상 N^{-1}(n)\subseteq P은 반사슬을 이루며, 이들은 P의 분할을 이룬다.

:P=\bigsqcup_{n=0}^\infty N^{-1}(n)

따라서 a(P)\le\operatorname{height}(P)이다.

4. 확장

딜워스 정리의 무한 부분 순서 집합에 대한 확장은, 부분 순서 집합의 폭이 ''w''인 것은 그 집합을 ''w''개의 체인으로 분할할 수 있을 때와 필요충분조건 관계에 있다고 설명한다. 무한 부분 순서 집합 ''P''의 폭이 ''w''라고 가정하면, 이는 모든 반사슬에 ''w''개 이하의 원소가 있다는 의미이다. ''P''의 임의의 부분 집합 ''S''에 대해, ''w''개의 체인으로의 분해 (존재하는 경우)는 ''S''의 비교 불가능 그래프( ''S''의 원소를 정점으로 하고, 비교 불가능한 두 원소 사이에 간선이 있는 그래프)를 ''w''개의 색으로 채색하는 것으로 나타낼 수 있다. 이때 비교 불가능 그래프의 적절한 채색에서 모든 색 클래스는 체인이 된다. ''P''의 폭이 ''w''라는 가정과 딜워스 정리의 유한 버전에 의해, ''P''의 모든 유한 부분 집합 ''S''는 ''w''-채색 가능한 비교 불가능 그래프를 갖는다. 따라서, 드 브루인-에르되스 정리에 의해, ''P'' 자체도 ''w''-채색 가능한 비교 불가능 그래프를 가지므로, 원하는 체인 분할을 갖는다.

그러나 이 정리는 폭뿐만 아니라 집합의 기수가 무한대인 부분 순서 집합에는 간단하게 확장되지 않는다. 이 경우, 가장 큰 반사슬의 크기와 부분 순서를 덮는 데 필요한 최소 체인의 수는 매우 다를 수 있다. 특히, 모든 무한 기수 κ에 대해, 가장 적은 수의 체인으로 분할했을 때 κ개의 체인을 갖는 폭이 ℵ0인 무한 부분 순서 집합이 존재한다.

5. 응용

비교 가능 그래프는 부분 순서 집합으로부터 각 원소에 대해 하나의 정점을 만들고, 서로 비교 가능한 두 원소에 해당하는 정점들을 연결하는 간선을 추가하여 만들어지는 무방향 그래프이다. 비교 가능 그래프에서 클리크는 체인에 해당하고, 독립 집합은 안티체인에 해당한다. 비교 가능 그래프의 모든 유도된 부분 그래프는 해당 부분 순서 집합의 부분 집합으로 제한하여 형성된 또 다른 비교 가능 그래프이다.

무방향 그래프에서 모든 유도된 부분 그래프의 색칠 수가 가장 큰 클리크의 크기와 같으면 완전 그래프라고 한다. 모든 비교 가능 그래프는 완전 그래프인데, 이는 미르스키의 정리를 그래프 이론 용어로 바꿔 말한 것과 같다.:143[1] 완전 그래프 정리에 따르면, 모든 완전 그래프의 여 그래프도 완전 그래프이다. 따라서 모든 비교 가능 그래프의 여 그래프는 완전 그래프이며, 이는 딜워스의 정리 자체를 그래프 이론 용어로 바꿔 말한 것이다.[1] 그러므로 완전 그래프의 여 그래프 속성은 딜워스의 정리에 대한 또 다른 증명을 제공한다.

불 대수 격자 ''B''''n''은 ''n''개의 원소를 가진 집합 ''X''(간단히 {1, 2, …, ''n''})의 멱집합을 포함 관계를 기준으로 정렬한 것이다. 이를 (2[''n''], ⊆)로 나타낸다. 스페르너 정리에 따르면, ''B''''n''의 최대 안티체인의 크기는 다음을 넘지 않는다.

:\operatorname{width}(B_n) = {n \choose \lfloor{n/2}\rfloor}.

즉, ''X''의 부분집합 중 서로 포함 관계가 없는 가장 큰 집합은 ''X''에서 원소 개수가 중간 정도인 부분집합들을 모아 얻을 수 있다. 루벨-야마모토-메샬킨 부등식은 멱집합 내의 안티체인과 관련이 있으며, 스페르너 정리를 증명하는 데 사용될 수 있다.

구간 [1, 2''n'']의 정수들을 나눗셈으로 정렬하면, 부분 구간 [''n'' + 1, 2''n'']은 크기가 ''n''인 안티체인을 이룬다. 이 부분 순서를 ''n''개의 체인으로 나누는 것은 간단하다. [1, 2''n'']의 각 홀수 ''m''에 대해, ''m''2''i'' 형태의 숫자들로 체인을 구성하면 된다. 따라서 딜워스의 정리에 의해 이 부분 순서의 너비는 ''n''이다.

단조 부분 수열에 관한 에르되스-세케레스 정리는 순서 차원이 2인 부분 순서에 딜워스 정리를 적용한 것으로 볼 수 있다.[2]

안티매트로이드의 "볼록 차원"은 안티매트로이드를 정의하는 데 필요한 최소 체인 개수로 정의되며, 딜워스 정리를 통해 관련 부분 순서의 너비와 같음을 알 수 있다. 이러한 관계는 볼록 차원을 다항 시간에 계산하는 알고리즘으로 이어진다.[3]

6. 역사

딜워스의 정리는 미국의 수학자 로버트 파머 딜워스(Robert Palmer Dilworth영어, 1914~1993)가 1950년 논문에서 처음 제시하였다.[3][4]

미르스키의 정리는 러시아 태생의 영국 수학자 레오니트 미르스키(Леонид Мирскийru, Leonid Mirsky영어, 1918~1983)가 1971년에 증명하였다.[5]

참조

[1] 저널 On Dilworth’s theorem in the infinite case 1963
[2] 저널 A proof of Dilworth’s theorem for partially ordered sets 1963
[3] 서적 새로운 조합수학 http://www.kyowoo.co[...] 교우사 2007
[4] 저널 A decomposition theorem for partially ordered sets 1950-01
[5] 저널 A dual of Dilworth’s decomposition theorem https://archive.org/[...] 1971


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

문의하기 : help@durumis.com