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.

REFERENCES:

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.