Constructing Chain Cover of Finite POSET

최근 jo_on님을 통해 알게 된 내용을 정리해 보았다.

 

Theorem (Dilworth). Finite POSET $P$에 대해, $P$의 minimum chain cover의 크기는 $P$의 maximum antichain의 크기와 같다.

 

이 글에서는 Dilworth's theorem의 constructive pf를 목표로 한다.

POSET과 Mirsky's theorem에 대해서는 전에 대충 써놓은 글이 있다.

---

1. Non-constructive proof

 

$\newcommand{\abs}[1]{| #1 |}$가장 잘 알려져 있는 증명법이기도 하다. Construction과는 그다지 관계가 없으니 관심없다면 스킵해도 될 듯.

$P$의 크기에 대해 귀납법을 사용하자. $P$의 maximum antichain $A$를 잡자. 이 때 $$A^{\uparrow} = \{ b \in P \mid \exists a \in A \text{ s.t. } b \ge a\}\\A^{\downarrow} = \{ b \in P \mid \exists a \in A \text{ s.t. } b \le a\}$$

를 잡으면, $A$가 maximal antichain이므로 $A^{\uparrow} \cap A^{\downarrow} = A$, $A^{\uparrow} \cup A^{\downarrow} = P$임을 확인할 수 있다.

 

먼저 $A^{\uparrow} \neq A$, $A^{\downarrow} \neq A$인 $A$가 하나라도 존재하는 경우를 보자. 이제 $A^{\uparrow}$와 $A^{\downarrow}$에 대해 귀납가정을 적용하여 $A^{\uparrow}$의 minimum chain cover $\mathcal{C}^{\uparrow}$, $\mathcal{C}^{\downarrow}$를 잡으면 두 chain cover의 크기가 정확히 $|A|$와 같고, 모든 $a \in A$에 대해 $a$를 포함하는 $\mathcal{C}^{\uparrow}$와 $\mathcal{C}^{\downarrow}$의 원소가 정확히 하나씩 존재한다. 이 chain들을 이어주면 성립.

 

나머지 경우는 모든 maximum antichain $A$가 minimal element의 집합이거나 maximal element의 집합이 된다. 일반성을 잃지 않고 $A^{\downarrow} = A$라고 하자. 즉 $A^{\uparrow} = P$이다. 아무 $a \in A$와, $a \le b$를 만족하는 maximal element $b \in P$를 잡자. $a\neq b$일 필요는 없다. 이 때 $P \backslash \{a,b\}$에는 크기가 \(\abs{A} - 1\)을 넘는 antichain이 존재할 수 없고, $A \backslash \{a\}$는 실제로 크기 \(\abs{A} - 1\)의 antichain이 된다. 따라서 $P \backslash \{a,b\}$에 귀납가정을 적용하면 크기 \(\abs{A} - 1\)의 chain cover를 찾을 수 있다. 여기에 chain $\{a,b\}$를 더하면 크기 \(\abs{A}\)의 chain cover를 찾을 수 있다.

 

따라서 minimum chain cover 크기가 maximum antichain의 크기보다 작거나 같다는 것을 확인할 수 있고, 반대쪽 부등식은 자명한 수준이므로 증명이 끝난다. 

 

2. Perfect Graph Theorem

이것도 non-constructive 증명이다. 되게 신기해서 넣었다 ㅋㅋ 몇가지 용어 정의가 필요하다.

 

Def. (Perfect Graph) 그래프 $G$의 최소 채색 수를 $\chi(G)$, maximum clique의 크기를 $\omega(G)$라고 하자. $\chi(G) \ge \omega(G)$는 항상 성립하는 사실이지만, 모든 induced subgraph $H$에 대해 $\chi(H) = \omega(H)$라면 $G$를 perfect graph라고 한다.

 

Thm. (Lovasz, Perfect Graph Theorem) 그래프 $G$가 perfect graph인 것은 $G$의 complement graph $\overline{G}$가 perfect graph인 것과 동치이다.

 

POSET $P$에 대해, $V(G) = P$이고 $uv \in E(G) \iff u < v \text{ or } v < u$인 comparability graph $G$를 잡자. 이 때 $G$의 coloring은 antichain cover에 대응되고, $G$의 clique은 하나의 chain에 대응된다. 따라서 Mirsky's theorem에 의해 $G$는 perfect graph가 된다.

 

이제 $\overline{G}$를 생각하면 $\overline{G}$의 coloring이 chain cover, clique가 antichain에 대응된다! 따라서 Perfect graph theorem에 의해 $\chi(\overline{G}) = \omega(\overline{G})$임을 알고, 이로부터 Dilworth's theorem을 증명할 수 있다.

 

3. Using Konig's theorem

Thm. (Konig) 이분그래프에서 maximum matching의 크기와 minimum vertex cover의 크기는 같다.

 

이건 첫 constructive proof이다. 적당히 그래프에서 maximum matching을 구해줌으로써 maximum chain cover를 실제로 만들 수 있다.

 

이분그래프 $G$가 $L$, $R$로 이분된다고 하고, $L$과 $R$을 구성하자.$a \in P$에 대해 $a_{1} \in L$과 $a_{2} \in R$을 정점으로 만들자. $a \le b \in P$에 대해 $a_{1}b_{2}$를 간선으로 이어준다.

 

이 때, 임의의 matching $M$에 대해 크기 $|P| - |M|$의 chain cover를 만들 수 있다. $v_{1} \notin M$에 해당하는 $v \in P$를 각 cover의 maximal element로 하는 chain cover를 만들 수 있다; $v_{2}$에서 매칭을 타고 $w_{1}$으로, $w_{2}$에서 매칭을 타고 $x_{1}$으로 .... 매칭이 없을 때까지 이어주면 된다. deg = 1이 강제된 구조인 matching과 chain 사이의 유사성을 실감할 수 있다.

 

Konig's theorem에 의해, 최대 매칭 $M$과 크기가 같은 vertex cover $C$가 존재한다. 이 때, $x_{1} \notin C \text{ and } x_{2} \notin C$를 만족하는 $x$들을 모은 집합 $A$는 antichain이 된다. $x \notin y \in A$가 비교 가능하다면 $x_{1}y_{2}$나 $x_{2}y_{1}$이 cover되지 않기 때문. 이 때 $|A| \ge |P| - |M|$이 되고, maximum antichain이 minimum chain cover보다 크거나 같다는 것을 알 수 있다. 반대 방향 부등식은 자명하므로 등식을 증명할 수 있다.

 

따라서 그래프에서 최대 매칭을 찾고, 그로부터 자연스럽게 유도되는 chain cover를 찾으면 된다. Minimum Vertex Cover도 적당히 찾아주면 maximum antichain도 구할 수 있는 것 같다.

 

4. Using MinFlow - MaxCut Theorem and a Weighted Variant

Minflow-MaxCut은 MaxFlow-Mincut의 dual인데, 간선에 upper bound (capacity)는 없고 lower bound (threshold)만 있는 경우, sink to source 경로가 없는 그래프 하에서 mininum flow와 max  directed cut이 같다는 정리이다. 이 문서 의 정리 3.7을 참조. 

 

3번 경우와 비슷하게 source $s$, sink $t$를 추가한 뒤 $a \in P$에 대해 $a_{1} \in L$과 $a_{2} \in R$을 정점으로 만들자. $a_{1} \to a_{2}$를 lower bound 1짜리 간선, $a \le b$에 대해 $a_{2} \to b_{1}$를 lower bound 0짜리 간선으로 이어준다. 이 경우 chain 하나가 크기 1의 augmenting path 하나에 대응되므로, minimum flow로부터 minimum chain cover를 바로 얻을 수 있다. 

 

이제 이 그래프의 directed cut $S$를 생각하자. $S \subset V$가 directed cut이라는 의미는 $s \in S, t \notin S$를 만족하고 (cut의 정의) $S$로 들어오는 간선이 없다는 것을 의미한다. 이 때 $a_{1} \in S, a_{2} \notin S$를 만족하는 $a$끼리는 antichain을 이룬다. 그렇지 않다면 directed cut의 정의에 모순. 또, Maximum Directed Cut은 Directed Cut 중, $S$에서 나가는 간선의 threshold 합이 가장 큰 cut을 의미한다. 이를 $S$의 threshold라 한다. 그런데 $S$의 threshold는 곧 $S$로부터 induce되는 antichain의 크기와 같다.

 

MinFlow - MaxCut theorem에 의해 Minimum flow의 net flow와, Maximum directed cut의 threshold가 같고, Dilworth's theorem이 이로부터 증명된다. Minimum Flow의 경우 그래프를 뒤집고 maximum flow를 푸는 것으로 해결할 수 있으므로, poly-time에 구할 수 있는 대상이다. 이 Minimum Flow를 이용하면 weighted minimum chain cover같은 걸 구할 수 있다.

 

Thm. (Weighted Mirsky) POSET의 Weight function $w : P \to \mathbb{Z}^{+}$에 대해, 임의의 $a \in P$에 대해 $a$를 정확히 $w(a)$번 cover하는 $P$의 minimum antichain cover의 크기는 $P$의 maximum weight antichain의 weight와 같다.

 

Thm. (Weighted Dilworth) 마찬가지로 $a$를 정확히 $w(a)$번 cover하는 minimum chain cover의 크기는 $P$의 maximum weight antichain의 weight와 같다.

 

증명은 $a$를 크기 $w(a)$짜리 chain으로 분해해서 할 수 있다. 그런데 구현할 때도 실제로 $w(a)$번 $a$를 복제하면 exponential 복잡도를 갖게 되는데, minflow-maxcut 증명에서 각 간선의 lower_bound를 $w(a)$로 바꾸면 똑같이 weighted minimum chain cover도 구할 수 있음을 알 수 있다. $\blacksquare$