The jump number of suborders of the power set order (Q583248): Difference between revisions

Let L be a linear extension of an ordered set P and \(x,y\in P\). The pair (x,y) is said to be a jump if the elements x, y are comparable in L but not in P. The number of these jumps is denoted by s(P,L) and min\(\{\) s(P,L)\(|\) L is a linear extension of \(P\}\) is denoted by s(P). If L is a linear extension of P with \(s(P)=s(P,L)\), then L is said to be optimal. Let S be an n-element set (n a positive integer) and \(B_ n\) denote the lattice of all subsets of S ordered by inclusion. For a subset \(\{\ell_ 1<\ell_ 2<...<\ell_ t\}\) of \(\{\) 0,1,...,n\(\}\) the ordered set \(B_ n(\ell_ 1,...,\ell_ t)\) is defined as the subset of \(B_ n\) of all subsets of S with cardinal numbers \(\ell_ 1,...,\ell_ t\). The main result gives the following formula: Theorem. \[ s(B_ n(\ell_ 1,...,\ell_ t))=- 1+\sum^{t}_{k=1}\left( \begin{matrix} n\\ \ell_ k\end{matrix} \right)- \sum^{t-1}_{k=1}\left( \begin{matrix} n-\ell_{k+1}+\ell_ k\\ \ell_ k\end{matrix} \right). \] Further, let S be linearly ordered. For \(A,B\in B_ n\) set \(A<_ LB\) if max((A\(\cup B)-(A\cap B))\in B\). Then \(<_ L\) is a linear order on \(B_ n\) (with equality), which is called a reverse lexicographic ordering of \(B_ n\). The former theorem has now an addition: ``Reverse lexicographic orderings of \(B_ n(\ell_ 1,...,\ell_ t)\) are optimal.''