Partial Order
A relation "
" is a
partial order on a set 
if it has:
1. Reflexivity: 
for all 
.
2. Antisymmetry: 
and 
implies
.
3. Transitivity: 
and 
implies
.
For a partial order, the size of the longest chain (antichain) is called the partial order length (partial order width). A partially ordered set is also called a poset.
A largest set of unrelated vertices in a partial order can be found using MaximumAntichain[g] in the Wolfram Language package Combinatorica` . MinimumChainPartition[g] in the Wolfram Language package Combinatorica` partitions a partial order into a minimum number of chains.
Contact the MathWorld Team
100!
