Maximum and minimum jump number of posets from matrices (Q1194526): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: On the minimum rank of regular classes of matrices of zeros and ones / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Jump Number of Dags and Posets: An Introduction / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A decomposition theorem for partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimizing Setups for Cycle-Free Ordered Sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Transversal theory. An account of some aspects of combinatorial mathematics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3851094 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders / rank | |||
Normal rank |
Latest revision as of 14:13, 16 May 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