TOPICS
Search

Partial Order


A relation "<=" is a partial order on a set S if it has:

1. Reflexivity: a<=a for all a in S.

2. Antisymmetry: a<=b and b<=a implies a=b.

3. Transitivity: a<=b and b<=c implies a<=c.

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.


See also

Antichain, Chain, Fence Poset, Linear Extension, Partial Order Ideal, Partial Order Length, Partial Order Width, Partially Ordered Set, Preorder, Total Order

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Partial Order

Cite this as:

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

Subject classifications