2018. 11. 4. 11:02ㆍ수학 이론/이산수학
Mirsky's theorem은 POSET에 관련된 기초적인(?) 정리 중 하나인데, 어디 심층 문제에 대뜸 나왔다길래 포스팅해본다.
이에 완전히 대응되는 정리로 Dilworth's theorem이 있지만 증명이 복잡해서 일단은 Mirsky만 증명하기로 한다.
POSET(PreOrder SET)의 형식적인 정의는 다음과 같다. 직관적으로는 두 정수 간의 약배수 관계를 생각하면 된다.
- 집합 의 원소들에 대해서, 관계 가 다음을 만족한다.
- 반사율 (reflexivity) : 임의의 에 대해 .
- 추이율 (transitivity) : 에 대해 .
반드시 모든 두 원소 에 대해 또는 가 성립할 필요는 없다.
정수의 약배수 관계에 대입해보면 약배수 관계가 두 조건을 충족한다는 것을 알 수 있다.
Mirsky's theorem을 이해하기 위해선 chain, antichain이라는 개념이 필요하다. 전혀 어렵지 않은 개념이지만 명쾌하면서도 엄밀한 설명을 쓰기는 언제나 어렵다.
Chain은 의 부분집합 중 임의의 두 원소를 비교할 수 있는 것을 말한다. 약배수 관계를 생각했을 때 는 의 chain을 이룬다.
Antichain은 반대로, 임의의 두 원소 간에 순서관계가 성립하지 않는 부분집합을 말한다. 약배수 관계로 생각했을 때 소수의 집합 은 의 antichain을 이룬다. 형식적으로는 이렇게 쓰는데 별로 유용하지는 않은 것 같으니 너무 얽매이지는 말자.
- Antichain 의 원소 에 대해, .
원소 1개짜리 집합(singleton)은 자명하게 chain이자 antichain이므로, 집합 를 chain, 혹은 antichain들로 분할할 수 있다. Mirsky's theorem은 이 분할의 크기와 관련된 정리이다.
Thms.
- Mirsky's theorem: \(C(P) = \left|\text{maximal_chain}(P)\right|\)가 finite할 때, \(C(P) = \left|\text{minimal_antichain_partition}(P)\right| = \text{ap}(P)\).
- Dilworth's theorem: \(A(P) = \left|\text{maximal_antichain}(P)\right|\)가 finite할 때, \(A(P) = \left|\text{minimal_chain_partition}(P)\right| = \text{cp}(P)\).
각각 와 가 infinite한 경우에는 성립하지 않는다고 한다. 이건 생각해보고 추가할 예정.
랑 를 실제로는 와 라고 쓰는데 맨날 둘이 헷갈려서 별로 좋아하지 않는다.
Proof of Mirsky's theorem
1.
를 분할하는 반사슬들을 라고 하자. ()
이 때 임의의 사슬 에 대해서 이 성립하므로 이다.
임의의 (사슬, 반사슬 분할)에 대해서 다음이 성립하므로 이다.
2.
이 부분이 간단하지만 tricky하다. 아이디어는 크기 이하의 antichain partition을 실제로 construct하는 것이다.
에 대해, 를 "를 극대 원소로 하는 chain의 최대 크기"로 정의하자.
극대 원소는 생각하는 그거 맞다. 인 가 없는 원소.
가령 에서 이다.
이 때 임의의 에 대해 의 preimage 은 antichain을 이룬다. 만약 인 이 존재한다면 이기 때문.
이때 의 범위가 이고, 가 의 분할을 이루므로 증명이 끝난다.
Corollary.
이걸 Chain - Antichain이라고 불렀던 것 같은데 왜 찾으면 안 나오는지 모르겠다.
- 가 finite할 때, .
증명은 한줄이다.
언젠가 Dilworth's theorem도 추가해야겠다. 신기한 증명법이 있다고 해서 연구해보려고 한다.
'수학 이론 > 이산수학' 카테고리의 다른 글
Ore's theorem & Palmer's algorithm (0) | 2019.08.17 |
---|---|
Bessel's Correction (Revised) (1) | 2019.03.27 |
LYM inequality와 Sperner's theorem (0) | 2018.07.23 |
High Girth & High Chromatic with Probabilistic method (0) | 2017.12.23 |
Beatty Sequence와 Rayleigh's theorem (0) | 2017.12.15 |