03914381

j

03914381 El-Zahar, M.H. Rival, I. Examples of jump-critical ordered sets. SIAM J. Algebraic Discrete Methods 6, 713-720 (1985). 1985 Society for Industrial and Applied Mathematics, Philadelphia, PA EN ordered sets linear extension of a finite ordered set jump number jump-critical sets gluing

doi:10.1137/0606069

The authors, who have done work on the problem treated in this paper before, continue with the study of (partially) ordered sets which they call "jump-critical". A jump in a linear extension of a finite ordered set is a pair of elements a, b such that $a\le b$ in the extension, while a is incomparable with b in the original order. The jump number is the minimal number of jumps occuring in any linear extension. An ordered set is called jump-critical if, taking away any element of it, the jump- number decreases. Obviously, any antichain is trivially jump-critical. Such sets with jump numbers 0, 1 and 2 are easy to find. Theorem 1 of the present paper enumerates the complete set of 14 jump- critical sets of jump number 3, the largest of which has 9 elements. The proof is by combinatorial arguments and case analysis. Theorem 2 is concerned with a process which the authors call gluing (and which has been used in lattice theory before). Gluing converts two ordered sets into a new one; the authors use it to obtain a new jump- critical set out of two given ones, with the jump-number of the constituents added (or added $-1$). The gluing process has been used to disprove several conjectures on the size of jump critical sets with given jump number m. The upper bound $(m+1)!$, proved by the first author and J. H. Schmerl in 1984, has not yet been bettered. P.Wilker