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\)