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.
Referencesedit
Trotter, W. T. (1992), Combinatorics and partially ordered sets: Dimension theory, Johns Hopkins Series in Mathematical Sciences, Baltimore: Johns Hopkins Univ. Press.
October 31, 2023
critical, pair, order, theory, order, theory, discipline, within, mathematics, critical, pair, pair, elements, partially, ordered, that, incomparable, that, could, made, comparable, without, requiring, other, changes, partial, order, hasse, diagram, partial, o. 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 lt c without requiring any other changes Conversely c b is not a critical pair since d lt c but not d lt 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 lt x then z lt y and for every z in S if y lt z then x lt 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 editTrotter W T 1992 Combinatorics and partially ordered sets Dimension theory Johns Hopkins Series in Mathematical Sciences Baltimore Johns Hopkins Univ Press Retrieved from https en wikipedia org w index php title Critical pair order theory amp oldid 1004424837, wikipedia, wiki, book, books, library,
