딜워스의 정리

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

딜워스의 정리(Dilworth's theorem, -定理)는 그래프 이론, 순서론, 조합적 집합론 등에서 다뤄지는 수학적 정리로, 미국의 수학자 로버트 팔머 딜워스(Robert Palmer Dilworth)가 1950년 논문에서 처음 제시하였다.[1]

공식화[편집]

딜워스의 정리는 다음과 같이 공식화할 수 있다.[1]

증명[편집]

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

  • a(P) ≤ c(P).

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

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

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

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

  1. P+ := {x∈P|x≥y, y∈W}
  2. P- := {x∈P|x≤y, y∈W}

분명히 P+≠P≠P-이므로, P+와 P-에 대해 귀납법 가정을 적용하여 P+와 P-를 각각 m개의 사슬로 분해할 수 있다. 정의에서 P+∩P- = W인데, W의 각 원소 y에 첨수 i를 붙일 때, y_i 가 P+의 극소원소이고 P-의 극대원소이기 때문에 각 사슬분해에서 P+의 분해 중 하나인 A_i 와 P-의 분해 중 하나인 B_i 가 존재하여 y_i 를 각각 극소원소, 극대원소로 갖는다. 따라서 모든 i에 대하여 A_iB_i 를 붙이면 P+∪P- = P이므로 P의 사슬분해를 얻는다. 즉, m = c(P)가 된다.

주석[편집]

  1. 윤영진, 《새로운 조합수학》, 교우사, 2007, 303쪽.
  2. 같은 책, 304쪽.

참고 문헌[편집]

  • 윤영진, 《새로운 조합수학》, 교우사, 2007