4.3 Maximal chains and antichains

Definition of maximal chains

A maximal chain in a partially ordered set (poset) is a chain that cannot be extended by adding any other element from the poset. In other words, there's no element you could insert into the sequence while keeping everything comparable. Maximal chains represent the longest possible "vertical paths" through a poset, and their length determines the poset's height.

Properties of maximal chains

• Every element in a maximal chain is comparable to every other element in that chain (pairwise comparability).
• You cannot add any element from the poset to a maximal chain and still have a chain. That's what makes it maximal.
• In a finite poset, a maximal chain always starts at a minimal element and ends at a maximal element.
• The height of a poset equals the length of its longest maximal chain. (Length here means the number of elements minus one, counting "steps" between elements.)
• Every chain in a poset can be extended to a maximal chain. In finite posets this is straightforward; in infinite posets, this relies on Zorn's Lemma.

Examples of maximal chains

• In the totally ordered set $\{1, 2, 3, 4, 5\}$, the entire set is itself the only maximal chain.
• In the power set of $\{a, b, c\}$ ordered by inclusion, one maximal chain is $\emptyset \subset \{a\} \subset \{a, b\} \subset \{a, b, c\}$. Notice it goes from the smallest element to the largest, adding one element at each step. Another maximal chain would be $\emptyset \subset \{b\} \subset \{b, c\} \subset \{a, b, c\}$.
• In the divisibility poset of the divisors of 60, the sequence $1 \mid 2 \mid 6 \mid 30 \mid 60$ is a maximal chain. You can verify that no other divisor of 60 can be inserted into this sequence while preserving divisibility at every step.

Definition of antichains

An antichain in a poset is a set of elements that are pairwise incomparable: no element in the set is related to any other element in the set by the partial order. While chains capture vertical structure, antichains capture horizontal structure. A maximal antichain is one where you cannot add any other element from the poset without introducing a comparable pair.

Properties of antichains

• Every pair of elements in an antichain is incomparable. Neither $a \leq b$ nor $b \leq a$ holds for any two distinct elements $a, b$ in the antichain.
• A maximal antichain cannot be extended: every element outside the antichain is comparable to at least one element inside it.
• The width of a poset is the size of its largest antichain.
• Any antichain intersects any chain in at most one element. This makes sense: if two elements from an antichain both appeared in a chain, they'd be comparable, contradicting the antichain property.

Examples of antichains

• In the power set of $\{a, b, c\}$ ordered by inclusion, the set $\{\{a\}, \{b\}, \{c\}\}$ is a maximal antichain. No singleton is a subset of another singleton, and every other subset in the poset is either contained in or contains at least one singleton.
• In the divisibility poset of positive integers, the set $\{2, 3, 5, 7\}$ is an antichain because no prime divides another prime. However, this is not a maximal antichain in the full divisibility poset since you could add more incomparable elements.
• In the divisors of 30 ordered by divisibility, the set $\{6, 10, 15\}$ is a maximal antichain of width 3.

Maximal chains vs antichains

Chains and antichains are complementary ways of looking at a poset's structure. Chains measure how "tall" the poset is; antichains measure how "wide" it is. Understanding both gives you a complete picture.

Similarities and differences

• Both maximal chains and maximal antichains share the property of maximality: neither can be extended within the poset while preserving their defining property.
• Chains connect comparable elements vertically; antichains collect incomparable elements horizontally.
• In a finite poset, every maximal chain runs from a minimal element to a maximal element. A maximal antichain has no such constraint on which "levels" its elements come from.
• A chain can intersect many different antichains (one element per antichain at most), but an antichain intersects each chain in at most one element.

Relationships between chains and antichains

Two deep theorems connect these structures:

• Dilworth's theorem: The maximum antichain size equals the minimum number of chains needed to cover the poset.
• Mirsky's theorem (the dual): The maximum chain length equals the minimum number of antichains needed to cover the poset.

These theorems tell you that the "width" and "height" of a poset aren't just descriptive measurements. They directly determine optimal decompositions.

Dilworth's theorem

Dilworth's theorem is one of the central results in order theory. It gives a precise min-max relationship: the largest "horizontal slice" of a poset determines exactly how many "vertical threads" you need to cover everything.

Statement of the theorem

In any finite poset, the size of a maximum antichain equals the minimum number of chains needed to partition the poset. If the width of the poset is $w$, then the poset can be partitioned into exactly $w$ disjoint chains, and no fewer.

Proof outline

The standard proof proceeds by strong induction on the number of elements in the poset:

1. Base case: A single-element poset has width 1 and is trivially covered by one chain.
2. Inductive step: Let $A$ be a maximum antichain of size $w$. Remove $A$ and consider the "upper set" (elements above some element of $A$) and "lower set" (elements below some element of $A$).
3. Apply the inductive hypothesis to these smaller posets. Each can be decomposed into $w$ chains.
4. Stitch the chains together through the elements of $A$ to get a $w$-chain partition of the original poset.

An alternative proof constructs a bipartite graph from the poset and applies König's theorem (or equivalently, Hall's Marriage Theorem) to find a matching that yields the chain decomposition.

Applications

• Scheduling: If tasks have precedence constraints forming a poset, the minimum number of parallel processors needed equals the width of the poset.
• Algorithm design: Finding minimum chain covers and maximum antichains can be reduced to bipartite matching, which runs in polynomial time.
• Combinatorics: Dilworth's theorem is used to prove results about set families, graph coloring, and interval scheduling.

Chain decomposition

A chain decomposition partitions a poset into disjoint chains so that every element belongs to exactly one chain. The goal is usually to minimize the number of chains used.

Concept and importance

By Dilworth's theorem, the minimum number of chains in any partition equals the width $w$ of the poset. A minimal chain decomposition reveals the poset's vertical structure: each chain represents a linearly ordered "thread," and the number of threads tells you the degree of incomparability.

Algorithms for chain decomposition

1. Bipartite matching approach: Create a bipartite graph where each element $x$ appears as a node on both sides. Add an edge from $x$ on the left to $y$ on the right whenever $x < y$. A maximum matching in this graph corresponds to a minimum chain decomposition. This runs in $O(n^{5/2})$ using Hopcroft-Karp.
2. Network flow: Model the same problem as a maximum flow instance. The min-cut gives the width, and the flow paths give the chains.
3. Greedy approach: Iteratively build chains by always extending the current chain with an available successor. This doesn't always produce an optimal decomposition, but it works well for special poset classes like interval orders.
4. Dynamic programming: For structured posets (e.g., posets derived from sequences), specialized DP algorithms can find optimal decompositions more efficiently.

Antichain decomposition

An antichain decomposition partitions a poset into disjoint antichains. This is the dual of chain decomposition.

Concept and importance

By Mirsky's theorem, the minimum number of antichains needed to partition a poset equals the height of the poset (the length of the longest chain). Each antichain in the decomposition corresponds to a "level" of elements that are mutually incomparable.

Algorithms for antichain decomposition

The most natural algorithm is iterative peeling:

1. Find all minimal elements of the poset. These form an antichain (no minimal element is below another).
2. Remove them from the poset.
3. Repeat on the remaining poset until all elements are assigned.

Each layer you peel off is an antichain, and the number of layers equals the height. This is closely related to topological sorting: the layers correspond to the "ranks" in a topological ordering. The algorithm runs in $O(n + m)$ time, where $n$ is the number of elements and $m$ is the number of relations.

Width and height of posets

Width and height are the two fundamental parameters that characterize a poset's shape.

Relationship to maximal chains

The height of a poset is the length of its longest chain (number of elements minus one). Equivalently, it's the number of antichains in a minimum antichain decomposition. Height captures the vertical complexity: a poset with large height has long dependency chains, which matters for things like critical path analysis in project scheduling.

Relationship to antichains

The width of a poset is the size of its largest antichain. Equivalently, it's the number of chains in a minimum chain decomposition (Dilworth's theorem). Width captures horizontal complexity: a poset with large width has many mutually incomparable elements, indicating a high degree of parallelism.

Sperner's theorem

Sperner's theorem is a classic result that pins down the maximum antichain size in one of the most important posets: the Boolean lattice.

Statement of the theorem

In the power set of an $n$-element set ordered by inclusion, the largest antichain consists of all subsets of size $\lfloor n/2 \rfloor$. The size of this antichain is the middle binomial coefficient:

$\binom{n}{\lfloor n/2 \rfloor}$

For example, when $n = 4$, the largest antichain is the collection of all $\binom{4}{2} = 6$ subsets of size 2. No subset of size 2 contains another subset of size 2, and you can't do better than 6.

Proof outline

The elegant proof uses the LYM inequality (Lubell-Yamamoto-Meshalkin):

1. Count the number of maximal chains in the Boolean lattice $\mathcal{B}_n$. There are exactly $n!$ such chains (each corresponds to a permutation of the $n$ elements).

2. Each subset of size $k$ belongs to exactly $k!(n-k)!$ maximal chains.

3. Since any antichain intersects each maximal chain at most once, summing over all elements of an antichain $\mathcal{A}$ gives: $\sum_{A \in \mathcal{A}} \frac{k_A!(n - k_A)!}{n!} \leq 1$, where $k_A = |A|$.

4. This simplifies to $\sum_{A \in \mathcal{A}} \frac{1}{\binom{n}{k_A}} \leq 1$, which is the LYM inequality.

5. Since $\binom{n}{k} \leq \binom{n}{\lfloor n/2 \rfloor}$ for all $k$, the antichain can have at most $\binom{n}{\lfloor n/2 \rfloor}$ elements.

Applications

• Extremal set theory: Sperner's theorem is the starting point for many results about set families with forbidden containment relations.
• Boolean function analysis: Bounds on antichain sizes translate to bounds on the complexity of monotone Boolean functions.
• Communication complexity: Antichain bounds in Boolean lattices appear in lower bound arguments for communication protocols.

Applications in combinatorics

Counting problems

• Linear extensions: A linear extension is a total order consistent with the partial order. Maximal chains in the poset of linear extensions connect to counting problems that are #P-complete in general but tractable for special poset classes.
• Ideals and filters: The number of downward-closed sets (ideals) in a poset is related to its antichain structure, since every antichain of a distributive lattice corresponds to an ideal via the bijection in Birkhoff's representation theorem.
• Enumeration of maximal chains: In graded posets like the Boolean lattice, the number of maximal chains has clean formulas. In general posets, enumeration can be exponential.

Optimization problems

• Weighted antichains: Given weights on elements, find an antichain of maximum total weight. This generalizes to linear programming over the antichain polytope.
• Scheduling with precedence constraints: Chain decompositions directly solve the problem of assigning tasks to the minimum number of processors when tasks have ordering requirements.
• Sorting partially ordered data: The number of comparisons needed to complete a partial order into a total order is related to the number and structure of maximal chains.

Computational complexity

Finding maximal chains

• Finding a single maximal chain is straightforward: start at any minimal element, repeatedly move to a successor, and stop when you reach a maximal element. This runs in $O(n + m)$ time.
• Enumerating all maximal chains can require exponential time because a poset can have exponentially many maximal chains. For example, the Boolean lattice $\mathcal{B}_n$ has $n!$ maximal chains.
• For graded posets and lattices, specialized enumeration algorithms can exploit the regular structure.

Finding maximal antichains

• Finding a maximum antichain in a finite poset reduces to bipartite matching (via Dilworth's theorem), so it runs in polynomial time.
• Enumerating all maximal antichains is #P-complete in general.
• For posets of bounded width, parameterized algorithms can enumerate maximal antichains more efficiently.

Extensions to infinite posets

Infinite maximal chains

Infinite posets introduce subtleties that don't arise in the finite case. An infinite chain may have no minimum or maximum element (consider the integers under their usual order). Zorn's Lemma guarantees that if every chain in a poset has an upper bound, then the poset has a maximal element, and consequently maximal chains exist. Properties like cofinality (the smallest cardinality of a cofinal subset) become important for characterizing the "shape" of infinite chains.

Infinite antichains

Dilworth's theorem does not directly generalize to infinite posets without additional set-theoretic assumptions. The infinite version requires careful handling:

• An infinite poset may have no maximum antichain in the usual sense.
• The width of an infinite poset is defined as the supremum of finite antichain sizes, which may be an infinite cardinal.
• Connections to cardinal arithmetic and the axiom of choice arise naturally. For instance, the infinite Ramsey theorem and Erdős-Szekeres type results provide partial analogues of finite decomposition theorems.
• Applications include studying function spaces, infinite-dimensional lattices, and the structure of ideals in rings.