Partially Ordered Sets

A partially ordered set, or poset, is a set together with a relation that captures the idea of one element preceding or being below another, without requiring all pairs to be comparable.

Definition

A partially ordered set is a set with a binary relation that is reflexive, antisymmetric, and transitive; elements may be comparable or incomparable under this relation.

Scope

This topic covers the axioms of partial order, Hasse diagrams, chains and antichains, maximal and minimal elements, order-preserving maps and duality, and the combinatorial structure theorems of Dilworth and Mirsky. It also introduces the Mobius function of a poset, the order-theoretic engine behind general inclusion-exclusion.

Core questions

• How is a precedence relation among elements axiomatized and drawn?
• How are a poset's elements partitioned into chains or antichains?
• What is the largest antichain or longest chain in a poset?
• How does the Mobius function generalize counting by inclusion-exclusion?

Key concepts

• Partial order axioms
• Hasse diagram
• Chains and antichains
• Maximal and minimal elements
• Dilworth's theorem
• Mobius function

Key theories

Dilworth's theorem

In any finite poset the minimum number of chains needed to cover all elements equals the maximum size of an antichain, a fundamental min-max duality with many combinatorial consequences.

Mobius function of a poset

Every locally finite poset carries a Mobius function that inverts summation over the order; Rota's theory makes this the unifying source of inclusion-exclusion and number-theoretic inversion.

Clinical relevance

Posets model task scheduling with dependencies, version and inheritance hierarchies, and preference and subsumption relations, while chain and antichain decompositions appear in scheduling and sorting algorithms.

History

Dilworth's 1950 chain-antichain theorem and Rota's 1964 foundations of Mobius functions transformed the combinatorial study of ordered sets into a central topic of modern discrete mathematics.

Key figures

• Robert Dilworth
• Gian-Carlo Rota
• Richard P. Stanley

Seminal works

• davey2002
• stanley2011

Frequently asked questions

What is a Hasse diagram?

It is a drawing of a finite poset in which each element is a point placed above those it covers, with edges only between covering pairs, so the order is read upward.

What is an antichain?

An antichain is a set of elements no two of which are comparable, such as a collection of subsets none of which contains another.