Critical pair (order theory)

Critical pair (order theory)

In order theory, a discipline within mathematics, a critical pair is a pair of elements in a partially ordered set that are incomparable but that could be made comparable without changing the order relationships of any other pairs of elements.

Formally, let P = (S, ≤) be a partially ordered set. Then a critical pair is an ordered pair (x, y) of elements of S with the following three properties:

If (x, y) is a critical pair then the binary relation obtained from P by adding the single order relation xy is also a partially ordered set. The required properties of a critical pair ensure that, when the relation xy is added, the addition does not cause any violations of the transitive property.

A set R of linear extensions of P is said to "reverse every critical pair" if, for every critical pair (x, y) of P, there exists a linear extension in R for which y occurs earlier than x. This property may be used to characterize realizers of partial orders: A nonempty set R of linear extensions is a realizer if and only if it reverses every critical pair.


  • Trotter, W. T. (1992), Combinatorics and partially ordered sets: Dimension theory, Johns Hopkins Series in Mathematical Sciences, Baltimore: Johns Hopkins Univ. Press.

Retrieved from : http://en.wikipedia.org/wiki/Critical_pair_(order_theory)