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 requiring any other changes to the partial order.

Hasse diagram of a partial order with a critical pair ⟨b,c⟩. Adding the grey line would make b<c without requiring any other changes. Conversely, ⟨c,b⟩ is not a critical pair, since d<c, but not d<b.

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:

• x and y are incomparable in P,
• for every z in S, if z < x then z < y, and
• for every z in S, if y < z then x < z.

If (x, y) is a critical pair, then the binary relation obtained from P by adding the single relationship x ≤ y is also a partial order. The properties required of critical pairs ensure that, when the relationship x ≤ y 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 a critical pair (x, y) in P if there exists a linear extension in R for which y occurs earlier than x. This property may be used to characterize realizers of finite partial orders: A nonempty set R of linear extensions is a realizer if and only if it reverses every critical pair.

References

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