Partial Order (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
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.
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
Cite this as:
Weisstein, Eric W. "Partial Order." FromMathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PartialOrder.html