Maximum and minimum jump number of posets from matrices (Q1194526): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q186111 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Matúš Harminc / rank | |||
Normal rank |
Revision as of 20:19, 10 February 2024
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