딜워스의 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

정의[편집]

딜워스의 정리에 따르면, 임의의 부분 순서 집합 (P,\le)반사슬의 최대 크기는 P를 사슬로 분해할 때의 최소 개수와 같다.[1]:303

증명[편집]

부분 순서 집합 P가 주어졌을 때, 이 부분집합으로서 반사슬의 최대 크기를 a(P), 사슬의 최소 개수를 c(P)라 하자. 먼저 P가 k개 사슬의 합집합이라면 P의 부분집합인 반사슬은 많아야 k개의 원소를 갖는다. 따라서, 다음 부등식이 성립한다.[1]:303

  • a(P) ≤ c(P).

따라서, 핵심적으로 증명해야 할 것은 a(P) ≥ c(P) 부분이다. 이 부분의 증명은 쾨니그의 정리를 이용한 기법 등 여러 방법이 있는데, 여기서는 [2]에 실린 증명 방법을 소개한다.[1]:303–304 원소의 수에 대한 수학적 귀납법을 사용하자. 우선 원소가 하나뿐인 집합에 대해서는 자명히 이 부등식이 성립한다. 이제 부등식이 |Q|<|P|인 모든 부분 순서 집합 Q에 대해 성립한다고 가정하자. mP의 반사슬의 최대 크기라 할 경우, 다음과 같이 두 가지 경우로 나눌 수 있다.

  1. 모든 극대 원소의 집합이나 모든 극소원소의 집합이 크기가 m인 반사슬일 경우
  2. 모든 극대 원소의 집합이나 모든 극소 원소의 집합이 아닌 크기가 m인 반사슬이 존재할 경우

1의 경우 모든 극대 원소와 극소 원소들을 한 쌍씩 극대 원소가 극소 원소보다 크게 짝지어 비교할 수 있다. 그렇지 않으면 크기가 m보다 더 큰 반사슬이 존재하게 되기 때문이다. 이때 극대 원소와 극소 원소의 한 쌍을 (a, b)라 하자. 그러면 P\setminus\{a,b\}이 크기가 m인 반사슬을 포함하는 경우 귀납 가정에 의해 부등식은 성립한다. 반면, 크기가 m인 반사슬을 포함하지 않으며, 크기가 m-1인 반사슬을 포함하는 경우 역시 귀납가정에 의해

m-1 = a(P \setminus\{a,b\}) \ge c(P \setminus \{a, b\})

이 된다. 이 경우 c(P\setminus\{a, b\}) = m-1개의 사슬에 \{a, b\}가 속한 사슬을 하나 더하면 Pm개로 분해되므로

m = c(P)

가 된다.

2의 경우 그러한 반사슬을 W라 하고, 다음과 같이 두 집합 P_+P_-를 정의하자.

P_+=\{x\in P\colon\exists y\in W\colon  x\ge y\}
P_+=\{x\in P\colon\exists y\in W\colon x\le y\}

분명히 P_+\ne P\ne P_-이므로, P_+P_-에 대해 귀납법 가정을 적용하여 P_+P_-를 각각 m개의 사슬로 분해할 수 있다. 정의에서

P_+\cap P_-=W

인데, W의 각 원소 y에 첨수 i를 붙일 때, y_iP_+의 극소 원소이고 P_-의 극대 원소이기 때문에 각 사슬분해에서 P_+의 분해 중 하나인 A_iP_-의 분해 중 하나인 B_i 가 존재하여 y_i 를 각각 극소 원소, 극대 원소로 갖는다. 따라서 모든 i에 대하여 A_iB_i 를 붙이면 P_+\cup P_-=P이므로 P의 사슬 분해를 얻는다. 즉,

m=c(P)

가 된다.

역사[편집]

미국의 수학자 로버트 파머 딜워스(영어: Robert Palmer Dilworth)가 1950년 논문에서 처음 제시하였다.[3][1]:303

참고 문헌[편집]

  1. (한국어) 윤영진 (2007년). 《새로운 조합수학》. 교우사. ISBN 978-89-8172-379-8
  2. (영어) Perles, Micha A. (1963년). On Dilworth’s theorem in the infinite case. 《Israel Journal of Mathematics》 1 (2): 108–109. doi:10.1007/BF02759806. MR0168497. Zbl 0115.01703.
  3. (영어) Dilworth, R. P. (1950년 1월). A decomposition theorem for partially ordered sets. 《Annals of Mathematics》 51: 161–166. JSTOR 1969503. Zbl 0038.02003. ISSN 0003-486X.

바깥 고리[편집]

같이 보기[편집]