Partially ordered sets and k-decomposability

To each finite partially ordered set \(\bar A = \{a_1,a_2,\ldots,a_n\}\) consisting of distinct elements, one assigns a set \(\tilde A\) of permutations of the indices \(1,2,\ldots,n\); \(\tilde A\) will include exactly those permutations with the property that: \(a_i<a_j\) for elements of \(\bar A\) implies \(i< j\). In the ordering of this collection by pairwise comparisons, there arises the problem of finding the greatest symmetric decomposition of \(\tilde A\) by a pair of complementary relations: \(a_1< a_n\) and \(a_1> a_n\). A set \(\tilde A\) of permutations is called \(k\)-decomposable if the number of elements of the lower part in the greatest symmetric decomposition of \(\tilde A\) is equal to \(k\). If one denotes by \(\tilde P_n\) the class of sets of permutations of degree \(n\) corresponding to partially ordered sets, and by \(P_n\) the class of all sets of permutations of degree \(n\), the problem consists in estimating the maximal power \(A(k,n)\) of a \(k\)-decomposable set of class \(\tilde P_n\). In an earlier paper, the author obtained an upper estimate for the power \(A(k,n)\) of the maximal \(k\)-decomposable set of permutations in the whole class \(P_n\) as \(A(k,n)\le \lambda(k,n)k\), where \(\lambda(k,n)\), as \(k\) goes from 1 to \(n!/2\), monotonically decreases from \(n -1 + 1/(n -1)\) to \(2\). Since \(\tilde P_n\subset P_n\), the estimate for \(A(k,n)\) is highly excessive. In this paper, some properties of the sets of class \(\tilde P\) in the large (completeness and weak regularity) are established. Exact values of \(\tilde A(k,n)\) for \(k \le 4\) are given. Obviously, \(\tilde A(k,n)\le 3k\).

Recommendations

Cited in

(8)

This page was built for publication: Partially ordered sets and \(k\)-decomposability

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