Chain and Antichain

In this article, I will talk about chains, antichains, and some properties of them. This is the content of [Richard A. Brualdi Introductory Combinatorics (5th Edition)] Section 5.3.

Definition

Definition 1. [Chain, Antichain]

Given a set $S$ with length $n$, and a nonempty collection $C = \{C_1, C_2, \cdots, C_m\}$ of subsets of $S$.

1. $C$ is a chain if $\forall 1 \leq i, j \leq m$ such that $i \neq j$, we have either $C_i \subset C_j$ or $C_j \subset C_i$. Also, for a given chain $C$, we call $C$ a maximum chain as $C$ contains all possible size of subsets of $S$;
2. $C$ is an antichain if $\forall 1 \leq i, j \leq m$ such that $i \neq j$, we have neither $C_i \subset C_j$ nor $C_j \subset C_i$. Sometimes, antichains are also called "antichain partition".

Dilworth's Theorem

It is clear that any nonempty collection is either a chain or an antichain. For chain, as we require every pair of $(C_i, C_j)$ has inclusion relationship, the length of maximum chain is clearly $n$. But what is the maximum length of an antichain?

Theorem 2. [Dilworth's theorem]

The maximum length of an antichain of a set $S$ with length $n$ is at most $\binom{n}{\lfloor{\frac{n}{2}}\rfloor}$.

Let's give a proof.

Proof for Dilworth's theorem^[1]

Given an antichain $\mathcal{A}$ of a set $S$ with $n$ elements. Let $\beta$ be the number of pairs $(A, C)$ such that $A$ is a subset of $S$, $C$ is a maximul chain, while $A \in \mathcal{A}$, $A \in C$.

First, let's focus on each $C$. For $(A_1, C_1)$ and $(A_2, C_2)$, if $C_1 = C_2$, $A_1$ and $A_2$ is contained in a same chain gives $A_1 \subseteq A_2$ or $A_1 \subseteq A_2$, while $A_1, A_2 \in \mathcal{A}$ gives neither $A_i \subset A_j$ nor $A_j \subset A_i$ as $\mathcal{A}$ is an antichain, therefore $A_1 = A_2$. This gives $\forall C_i \in C$, there is at most one $(A, C_i)$ such that $A \in \mathcal{C}$, gives $\beta \leq n!$.

Now, we consider each $A$. For each $A$ with length $k$, it's clear that the number of maximal chains that contains $A$ is $k!(n-k)!$.

Then, let $\alpha _k$ be the number of $A$ with length $k$ in $\mathcal{A}$, we have $\beta = \sum_{k=0}^{n} \alpha _k k!(n-k)!$. Applying $\beta \leq n!$, we have:

$$ \sum_{k=0}^{n} \alpha _k k!(n-k)! \leq n! $$

$$ \sum_{k=0}^{n} \alpha _k \frac{k!(n-k)!}{n!} \leq 1 $$

$$ \sum_{k=0}^{n} \frac{\alpha _k}{\binom{n}{k}} \leq 1 $$

Since $\binom{n}{k} \leq \binom{n}{\lfloor{\frac{n}{2}}\rfloor}$ (this can be proved by induction), we have: $$ \sum_{k=0}^{n} \frac{\alpha _k}{\binom{n}{\lfloor{\frac{n}{2}}\rfloor}} \leq \sum_{k=0}^{n} \frac{\alpha _k}{\binom{n}{k}} \leq 1 $$ $$ \sum_{k=0}^{n} \alpha _k \leq \binom{n}{\lfloor{\frac{n}{2}\rfloor}} $$

Since $\sum_{k=0}^{n} \alpha _k = |\mathcal{A}|$, we have $|\mathcal{A}| \leq \binom{n}{\lfloor{\frac{n}{2}\rfloor}}$. This completes the proof.

TBD: Proof of The maximum chain length = The minimum antichain partition

References

1. Richard A. Brualdi - Introductory Combinatorics (5th Edition) ↩