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 with length , and a nonempty collection of subsets of .

is a chain if such that , we have either or . Also, for a given chain , we call a maximum chain as contains all possible size of subsets of ;
is an antichain if such that , we have neither nor . 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 has inclusion relationship, the length of maximum chain is clearly . But what is the maximum length of an antichain?

Theorem 2. Dilworth's theorem

The maximum length of an antichain of a set with length is at most .

Let's give a proof.

Proof for Dilworth's theorem¹

Given an antichain of a set with elements. Let be the number of pairs such that is a subset of , is a maximul chain, while , .

First, let's focus on each . For and , if , and is contained in a same chain gives or , while gives neither nor as is an antichain, therefore . This gives , there is at most one such that , gives .

Now, we consider each . For each with length , it's clear that the number of maximal chains that contains is .

Then, let be the number of with length in , we have . Applying , we have:

Since (this can be proved by induction), we have:

Since , we have . This completes the proof.

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

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