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, \leq)$ 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 \leq y$ is also a partial order. The properties required of critical pairs ensure that, when the relationship $x \leq 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.