딜워스의 정리

조합론에서 딜워스의 정리(Dilworth의定理, )는 부분 순서 집합의 반사슬의 최대 크기에 대한 정리다.

 정의 
부분 순서 집합 의 높이()는  속의 사슬(부분 전순서 집합)의 크기의 상한이다. 즉, 다음과 같다.

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

(여기서 은 두 원소가 비교 불가능임을 뜻한다.)

임의의 부분 순서 집합 에 대하여, 를 사슬들로 분할할 수 있으며, 이러한 분할의 최소 크기를 라고 하자. 또 를 반사슬들로도 분할할 수 있으며, 이러한 분할의 최소 크기를 라고 하자. 한원소 집합은 사슬이자 반사슬이므로, 자명하게

이다.

딜워스의 정리에 따르면, 만약 부분 순서 집합 의 너비가 유한하다면, 이는 와 같다. 반대로, 미르스키의 정리()에 따르면, 만약 의 높이가 유한하다면, 이는 와 같다.

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

 증명 
부분 순서 집합  속의 사슬  및 반사슬 에 대하여 이다. 따라서, 만약 를 사슬 들로 분할하였을 때, 각 반사슬 에 대하여 이므로 이며, 즉

이다. 반대로, 만약 를 반사슬 들로 분할하였을 때, 각 사슬 에 대하여 이므로 이며, 즉

이다.

따라서, 딜워스의 정리와 미르스키의 정리에서 자명하지 않은 것은 반대 방향의 부등식이다. 이 경우, 두 정리의 증명은 매우 다르다.

 딜워스의 정리 
딜워스의 정리의 증명은 쾨니그의 정리를 이용한 기법 등 여러 방법이 있다. 만약 가 유한 집합일 경우, 미카 아셰르 페를레스(, 1936~)는 다음과 같은 간단한 증명을 제시하였다.

유한 부분 순서 집합 가 주어졌다고 하자. 의 극대 원소들의 집합을 , 극소 원소들의 집합을 라고 하자. 이들은 각각 반사슬을 이룬다.

집합의 크기에 대한 수학적 귀납법을 사용하자. 우선, 딜워스의 정리는 한원소 집합인 부분 순서 집합에 대하여 자명하게 성립한다. 이제 딜워스의 정리가 크기  미만의 모든 부분 순서 집합에 대하여 대해 성립한다고 가정하자. 그렇다면, 다음과 같이 두 가지 경우로 나눌 수 있다.
 크기 의 반사슬은 모두 과 같거나, 와 같다.
  및 와 같지 않은, 크기 의 반사슬 가 존재한다.
1의 경우, 인 와 를 찾을 수 있다. (그렇지 아니하다면 크기가 보다 더 큰 반사슬이 존재하게 되기 때문이다.) 의 최소 사슬 분할

이 주어졌을 때

는 의 사슬 분할이므로, 에 딜워스의 정리를 적용하면

이다.

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

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

그렇다면 의 사슬 분해

를 얻는다. 즉,

가 된다.

 미르스키의 정리 
미르스키의 정리의 증명은 딜워스의 정리의 증명보다 더 간단하다. 가 유한한 높이의 부분 순서 집합이라고 하자. 원소 에 대하여, 가 를 최대 원소로 하는 사슬의 길이의 최댓값이라고 하자. 이는 함수 을 정의한다.
그렇다면, 각 자연수 의 원상 은 반사슬을 이루며, 이들은 의 분할을 이룬다.

따라서 이다.

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

미르스키의 정리는 러시아 태생의 영국 수학자 레오니트 미르스키(, , 1918~1983)가 1971년에 증명하였다.

 각주 

 외부 링크 






 같이 보기 
 쾨니그의 정리

분류:순서론
분류:조합적 집합론
분류:조합론 정리
분류:완벽 그래프