딜워스의 정리

1. 개요

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

2. 정의

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

부분 순서 집합 $(P,\backslash le)$의 너비(width^영어)는 $P$ 속의 반사슬의 크기의 상한이다. 즉, 다음과 같다.
:$\backslash operatorname\{width\}P=\backslash sup\backslash left\backslash \{|S|\backslash colon\; S\backslash subseteq\; P,\backslash ;s\backslash parallel\; s\text{'}\backslash forall\; s,s\text{'}\backslash in\; S\backslash right\backslash \}\backslash in\backslash mathbb\; Z^+\backslash cup\backslash \{0,\backslash infty\backslash \}$
(여기서 $s\backslash parallel\; s\text{'}$은 두 원소가 비교 불가능함을 뜻한다.)

임의의 부분 순서 집합 $P$에 대하여, $P$를 사슬들로 분할할 수 있으며, 이러한 분할의 최소 크기를 $c(P)$라고 하자. 또 $P$를 반사슬들로도 분할할 수 있으며, 이러한 분할의 최소 크기를 $a(P)$라고 하자. 한원소 집합은 사슬이자 반사슬이므로, 자명하게 다음이 성립한다.
:$c(P)\backslash le|P|$
:$a(P)\backslash le|P|$

딜워스의 정리에 따르면, 만약 부분 순서 집합 $(P,\backslash le)$의 너비가 유한하다면, 이는 $c(P)$와 같다. 반대로, 미르스키의 정리(Mirsky’s theorem^영어)에 따르면, 만약 $P$의 높이가 유한하다면, 이는 $a(P)$와 같다.
:
:

이 정리들은 무한한 너비 또는 높이의 부분 순서 집합에 대하여 기수로서 성립하지 않는다.

부분 순서 집합 $(P,\backslash le)$ 속의 사슬 $C\backslash subseteq\; P$ 및 반사슬 $A\backslash subseteq\; P$에 대하여 $|A\backslash cap\; C|\backslash le1$이다. 따라서, 만약 $P$를 사슬 $\backslash \{C\_i\backslash \}\_\{i\backslash in\; I\}$들로 분할하였을 때, 각 반사슬 $A\backslash subseteq\; P$에 대하여 $|C\_i\backslash cap\; A|\backslash le\; 1$이므로 $|A|\backslash le|I|$이며, 즉 다음이 성립한다.
:$\backslash operatorname\{width\}P\backslash le\; c(P)$


반대로, 만약 $P$를 반사슬 $\backslash \{A\_j\backslash \}\_\{j\backslash in\; J\}$들로 분할하였을 때, 각 사슬 $C\backslash subseteq\; P$에 대하여 $|C\backslash cap\; A\_j|\backslash le\; 1$이므로 $|C|\backslash le|J|$이며, 즉 다음이 성립한다.
:$\backslash operatorname\{height\}P\backslash le\; a(P)$

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²)에 인식될 수 있다.

3.1. 딜워스의 정리 증명

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

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

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

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

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

:$P\backslash setminus\backslash \{a,b\backslash \}=\backslash bigsqcup\_\{i=1\}^\{c(P\backslash setminus\backslash \{a,b\backslash \})\}C\_i$

이 주어졌을 때

:$P=\backslash \{a,b\backslash \}\backslash sqcup\; \backslash bigsqcup\_\{i=1\}^\{c(P\backslash setminus\backslash \{a,b\backslash \})\}C\_i$

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

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

이다.

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

:$A\_+=\backslash \{x\backslash in\; P\backslash colon\backslash exists\; a\backslash in\; A\backslash colon\; x\backslash ge\; a\backslash \}$
:$A\_-=\backslash \{x\backslash in\; P\backslash colon\backslash exists\; a\backslash in\; A\backslash colon\; x\backslash le\; a\backslash \}$
:$\backslash operatorname\{width\}(A\_+)=\backslash operatorname\{width\}(A\_-)=|A|=\backslash operatorname\{width\}P$
:$A\_+\backslash subsetneq\; P\backslash supsetneq\; A\_-$
:$A\_+\backslash cap\; A\_-=A$

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

:$A\_\backslash pm=\backslash bigsqcup\_\{a\backslash in\; A\}C\_\backslash pm(a)$
:$\backslash max\; C\_-(a)=a=\backslash min\; C\_+(a)$

그렇다면 $P$의 사슬 분해

:$P=\backslash bigsqcup\_\{a\backslash in\; A\}(C\_+(a)\backslash cup\; C\_-(a))$

를 얻는다. 즉,

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

가 된다.

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

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

귀납법에 의해, 정수 $k$에 대해 부분 순서 집합 $P\text{'}:=P\backslash setminus\backslash \{a\backslash \}$가 $k$개의 서로소인 체인 $C\_1,\backslash dots,C\_k$로 덮일 수 있고, 크기 $k$의 적어도 하나의 안티체인 $A\_0$을 갖는다고 가정한다. 분명히 $i=1,2,\backslash dots,k$에 대해 $A\_0\backslash cap\; C\_i\backslash ne\backslash emptyset$이다. $i=1,2,\backslash dots,k$에 대해, $x\_i$를 $P\text{'}$에서 크기 $k$의 안티체인에 속하는 $C\_i$의 극대 원소로 하고, $A:=\backslash \{x\_1,x\_2,\backslash dots,x\_k\backslash \}$로 설정한다.

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

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

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

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

3.2. 미르스키의 정리 증명

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

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

:$P=\backslash bigsqcup\_\{n=0\}^\backslash infty\; N^\{-1\}(n)$

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

4. 확장

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

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

5. 응용

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

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

불 대수 격자 B_n은 n개의 원소를 가진 집합 X(간단히 {1, 2, …, n})의 멱집합을 포함 관계를 기준으로 정렬한 것이다. 이를 (2^[n], ⊆)로 나타낸다. 스페르너 정리에 따르면, B_n의 최대 안티체인의 크기는 다음을 넘지 않는다.
:$\backslash operatorname\{width\}(B\_n)\; =\; \{n\; \backslash choose\; \backslash lfloor\{n/2\}\backslash rfloor\}.$
즉, X의 부분집합 중 서로 포함 관계가 없는 가장 큰 집합은 X에서 원소 개수가 중간 정도인 부분집합들을 모아 얻을 수 있다. 루벨-야마모토-메샬킨 부등식은 멱집합 내의 안티체인과 관련이 있으며, 스페르너 정리를 증명하는 데 사용될 수 있다.

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

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

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

6. 역사

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

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