Technical Report 275-1991
- Title
- Bounds for the Jump Number of Partially Ordered Sets
- Author
- Publication
- Methods of Operations Research, vol. 64, 1991, pp. 117-121
- Source
-
The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
- Classification
-
not available
- Keywords
-
not available
-
Every linear extension L of a partially ordered set P exhibits a chain partition of P, viz. the partition into maximal blocks of successive (with respect to L) comparable elements. The minimal number of chains needed is the jump number of P (denoted by s(P)) increased by 1. The jump number problem i.e. the computation of s(P) is known to be cal NP hard. This motivates the search for good bounds. There are two well known bounds for s(P). In this paper we generalize the defect-bound and improve the width-bound. Comparisons between the bounding parameters are exhibited through inequalities and examples. One of our parameters gives the exact value of s(P) for the class of 2-dimensional lattices, but unfortunately the computation of this bound seems to be hard again.