Maximum and minimum jump number of posets from matrices

DOI10.1016/0024-3795(92)90030-EMaRDI QIDQ1194526zbMATH OpenFDO

Authors Richard A. Brualdi, Hyung Chan Jung

Publication date 27 September 1992

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(92)90030-E

zbMATH Keywords

jump numberlinear extension of a poset

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorics of partially ordered sets (06A07)

Review text

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)\).

Recommendations

• scientific article; zbMATH DE number 2217189
• Matrices of zeros and ones with the maximum jump number
• On jump-critical posets with jump-number equal to width
• scientific article; zbMATH DE number 952655
• On minimizing jumps for ordered sets

Cites work

• A decomposition theorem for partially ordered sets
• A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders
• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• Minimizing Setups for Cycle-Free Ordered Sets
• On the minimum rank of regular classes of matrices of zeros and ones
• The Jump Number of Dags and Posets: An Introduction
• Transversal theory. An account of some aspects of combinatorial mathematics

Cited in

(6)

• Jump number problem: The role of matroids
• Matrices of zeros and ones with the maximum jump number
• On jump-critical posets with jump-number equal to width
• scientific article; zbMATH DE number 952655 (Why is no real title available?)
• scientific article; zbMATH DE number 1836188 (Why is no real title available?)
• scientific article; zbMATH DE number 2217189 (Why is no real title available?)

This page was built for publication: Maximum and minimum jump number of posets from matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1194526)