Maximum and minimum jump number of posets from matrices (Q1194526)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Maximum and minimum jump number of posets from matrices |
scientific article |
Statements
Maximum and minimum jump number of posets from matrices (English)
0 references
27 September 1992
0 references
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)\).
0 references
jump number
0 references
linear extension of a poset
0 references