Maximum and minimum jump number of posets from matrices (Q1194526): Difference between revisions

A jump in a linear extension \(L\) of a given poset \(P\) is a pair of elements which are incomparable in \(P\) and consecutive in \(L\). The jump number of \(P\) is the minimum number of jumps in any linear extension \(L\) of \(P\). Denote by \(A(n,k)\) the set of all \(k\)-regular bipartite posets with \(n\) minimal and \(n\) maximal elements and denote \(m(n,k)=\min\{\text{jump number of } P:\;P\in A(n,k)\}\), \(M(n,k)=\max\{\text{jump number of } P:\;P\in A(n,k)\}\). The authors use the matrix language to find the values or the boundaries for \(m(n,k)\) and \(M(n,k)\). They introduce and apply the so-called normal form of the matrix corresponding to a given poset \(P\). They have proved that if \(l=k=n\), then \(m(n,k)=n+k-2\). From the results presented in the paper the precise values of \(M(n,k)\) are obtained for \(l=n=k=10\). This well-written article contains some more results and conjectures concerning \(M(n,k)\).