Mirsky's theorem

2018. 11. 4. 11:02수학 이론/이산수학

Mirsky's theorem은 POSET에 관련된 기초적인(?) 정리 중 하나인데, 어디 심층 문제에 대뜸 나왔다길래 포스팅해본다.

이에 완전히 대응되는 정리로 Dilworth's theorem이 있지만 증명이 복잡해서 일단은 Mirsky만 증명하기로 한다.


POSET(PreOrder SET)의 형식적인 정의는 다음과 같다. 직관적으로는 두 정수 간의 약배수 관계를 생각하면 된다.


- 집합 PP의 원소들에 대해서, 관계 \preccurlyeq가 다음을 만족한다.

- 반사율 (reflexivity) : 임의의 aPa \in P에 대해 aaa \preccurlyeq a.

- 추이율 (transitivity) : a,b,cPa, b, c \in P에 대해 ab  bc    aca \preccurlyeq b \ \wedge \ b \preccurlyeq c \implies a \preccurlyeq c.


반드시 모든 두 원소 a,bPa, b \in P에 대해 aba \preccurlyeq b 또는 bab \preccurlyeq a가 성립할 필요는 없다.

정수의 약배수 관계에 대입해보면 약배수 관계가 두 조건을 충족한다는 것을 알 수 있다.


Mirsky's theorem을 이해하기 위해선 chain, antichain이라는 개념이 필요하다. 전혀 어렵지 않은 개념이지만 명쾌하면서도 엄밀한 설명을 쓰기는 언제나 어렵다.


Chain은 PP의 부분집합 중 임의의 두 원소를 비교할 수 있는 것을 말한다. 약배수 관계를 생각했을 때 {1,2,22,23,2k,}\{1, 2, 2^{2}, 2^{3}, \ldots 2^{k}, \ldots \}N\mathbb{N}의 chain을 이룬다.


Antichain은 반대로, 임의의 두 원소 간에 순서관계가 성립하지 않는 부분집합을 말한다. 약배수 관계로 생각했을 때 소수의 집합 {2,3,5,7,}\{2,3,5,7,\ldots\}N\mathbb{N}의 antichain을 이룬다. 형식적으로는 이렇게 쓰는데 별로 유용하지는 않은 것 같으니 너무 얽매이지는 말자.


- Antichain AA의 원소 a,ba,b에 대해, ab    a=ba \preccurlyeq b \implies a = b.


원소 1개짜리 집합(singleton)은 자명하게 chain이자 antichain이므로, 집합 PP를 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)\).


각각 C(P)C(P)A(P)A(P)가 infinite한 경우에는 성립하지 않는다고 한다. 이건 생각해보고 추가할 예정.

C(P)C(P)A(P)A(P)를 실제로는 height(P)\text{height}(P)width(P)\text{width}(P)라고 쓰는데 맨날 둘이 헷갈려서 별로 좋아하지 않는다.


Proof of Mirsky's theorem


1. C(P)ap(P)C(P) \le \text{ap}(P)


PP를 분할하는 반사슬들을 A1,A2,,AkA_{1}, A_{2}, \ldots, A_{k}라고 하자. (kap(P)k \ge \text{ap}(P))

이 때 임의의 사슬 CC에 대해서 CAi1\left| C \cap A_{i} \right| \le 1이 성립하므로 Ck|C| \le k이다.

임의의 (사슬, 반사슬 분할)에 대해서 다음이 성립하므로 C(P)ap(P)C(P) \le \text{ap}(P)이다.


2. C(P)ap(P)C(P) \ge \text{ap}(P)


이 부분이 간단하지만 tricky하다. 아이디어는 크기 C(P)C(P) 이하의 antichain partition을 실제로 construct하는 것이다.


xPx \in P에 대해, f(x)f(x)를 "xx를 극대 원소로 하는 chain의 최대 크기"로 정의하자. 

극대 원소는 생각하는 그거 맞다. x yx \preccurlyeq yyy가 없는 원소.

가령 N\mathbb{N}에서 f(8)=4={1,2,4,8}f(8) = 4 = |\{1,2,4,8\}|이다.


이 때 임의의 nn에 대해 nn의 preimage f1(n)={xPf(x)=n}f^{-1}(n) = \{ x \in P | f(x) = n \}은 antichain을 이룬다. 만약 xy,xyx \preccurlyeq y, x \neq yx,yf1(n)x, y \in f^{-1}(n)이 존재한다면 f(y)>nf(y) > n이기 때문.


이때 f(x)f(x)의 범위가 [1,C(P)][1, C(P)]이고, f1(1),,f1(C(P))f^{-1}(1), \ldots, f^{-1}\left( C(P) \right) PP의 분할을 이루므로 증명이 끝난다.


Corollary.


이걸 Chain - Antichain이라고 불렀던 것 같은데 왜 찾으면 안 나오는지 모르겠다.


- C(P),A(P)C(P), A(P)가 finite할 때, C(P)A(P)PC(P) \cdot A(P) \ge |P|.


증명은 한줄이다. C(P)A(P)=ap(P)A(P)P.C(P) \cdot A(P) = \text{ap}(P) \cdot A(P) \ge |P|._{\blacksquare}


언젠가 Dilworth's theorem도 추가해야겠다. 신기한 증명법이 있다고 해서 연구해보려고 한다.