Bounds for the Jump Number of Partially Ordered Sets
Stefan Felsner · 2008
A linear extension of a partial order P is a linear order L = x1, x2..., xn respecting the order relations of P, i.e. xi < xj implies i < j for all xi, xj ∈ P. In other words, L is the linear sum L = C0 ⊕ C1 ⊕... ⊕ Cm of disjoint chains C0, C1,..., Cm in P, whose union is all of P, such that x ∈ Ci, x ′ ∈ Cj and x < x ′ implies i ≤ j. We may assume the chains to be maximal, i.e. the last element of Ci, maxCi, is noncomparable with the first element of Ci+1, min Ci+1. The pairs (maxCi, min Ci+1) then are the jumps of P. The number of jumps of L is denoted by sP(L) and the jump number of P is s(P) = min{sP(L) : L is a linear extension of P}. The problem of determining the jump number has been shown to be NP-hard by Pulleyblank [Pu], his result motivates the study of lower bounds for s(P).