Discrete Mathematics - Lecture notes https://www.isibang.ac.in/~d.yogesh/Course_Notes/DM1/main.pdf.7.5 ***Some applications***8.1 Chains and Antichains in Set systems

Chapter 8 Extremal Set theory

Recall from Section 5.1 that a poset is a set $P$ with a binary relation $\leq$ that is reflexive and anti-symmetric. The binary relation is called as partial order and it is said to be a total order or linear order if any two elements are comparable. Further recall that a chain in a poset is a totally ordered set of $P$ and an antichain is a subset where no two elements are comparable. We will prove some results on chains and anti-chains complementing the results in Section 5.1. An easy visual representation of posets is via the Hasse diagram as follows:

Refer to caption — Figure 8.1: Hasse diagrams of four different posets.

We start with the more famous version of Dilworth’s decomposition theorem .

Theorem 8.1 (R. Dilworth (1950)).

Let $P$ be a finite poset. Let $m$ be the minimum number of disjoint chains whose union is $P$ and let $M$ be the maximum number of elements in an antichain of $P$ . Then $m=M$ .

Proof.

(H. Tverberg, 1967) Let $\{a_{1},\ldots,a_{M}\}$ be an anti-chain. Since each $a_{i}$ can belong to at most one chain, each $a_{i}$ must belong to a different chain and hence we need at least $M$ disjoint chains to cover $P$ i.e., $m\geq M$ .

For the other inequality, we use induction on $|P|$ . If $|P|=0,1$ there is nothing to prove. Let $|P|>1$ and let $C$ be a maximal chain in $P$ .

If the maximum number of elements in an anti-chain in $P\setminus C$ is at most $M-1$ , then by induction hypothesis $P\setminus C$ is a union of at most $M-1$ disjoint chains and so $P$ is a union of at most $M$ disjoint chains and so $m\leq M$ . The proof is complete.

Suppose, there is an anti-chain $\{a_{1},\ldots,a_{M}\}$ in $P\setminus C$ . Observe that this is a maximal anti-chain. Now define $S^{-}=\{x\in P:x\leq a_{i}\,\mbox{for some}\,i\}.$ Define $S^{+}$ analogously using $\geq$ . Since $\{a_{1},\ldots,a_{M}\}$ is a maximal chain, $S^{-}\cup S^{+}=P$ . Also by maximality of $C$ , the maximum (resp. minimum) element of $C$ does not belong to $S^{-}$ (resp. $S^{+}$ ). Thus by induction hypothesis both $S^{-}$ and $S^{+}$ are union of $M$ disjoint chains $S_{i}^{-},i=1,\ldots,M$ and $S_{i}^{+},i=1,\ldots,M$ respectively with $a_{i}\in S_{i}^{-}\cap S_{i}^{+}$ . Since $a_{i}$ ’s form an anti-chain, $a_{i}$ is the maximum element in $S_{i}^{-}$ and minimum element in $S_{i}^{+}$ . Thus $S_{i}=S_{i}^{-}\cup S_{i}^{+}$ is also a chain and further $S_{i}$ ’s are disjoint. Hence $P=\cup_{i}S_{i}$ and $m\leq M$ as required. ∎

Recall Dilworth’s earlier theorem (Theorem 5.2) Mirsky’s lemma (Lemma 5.3), which can both be considered as dual to the Dilworth’s theorem.

Exercise(A) 8.2.

Prove Hall’s matching theorem using Dilworth’s theorem.