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 Mathematica package Combinatorica`) . MinimumChainPartition[g] in the Mathematica package Combinatorica`) partitions a partial order into a minimum number of chains.

Ruskey, F. "Information on Linear Extension." http://www.theory.csc.uvic.ca/~cos/inf/pose/LinearExt.html.

Skiena, S. "Partial Orders." §5.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 203-209, 1990.

CITE THIS AS:

Weisstein, Eric W. "Partial Order." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PartialOrder.html