Interval stability and interval covering property in finite posets (Q1803666): Difference between revisions

In this paper the parameters \(\alpha\) and \(\rho\) of a finite ranked poset \(P\) measure the maximum size of a subset of \(P\) such that no two elements belong simultaneously to some interval of \(P\) and the minimum number of intervals covering all the elements of \(P\), respectively. It is shown that with input \((P,K)\), the problem of deciding \(\alpha\geq k\), \(\rho\leq k\) is NP-complete (T1). After that, conditions for \(\alpha=\rho\) are determined (T2). Next, refinements are introduced by introducing posets \(P_{(\ell,u)}=\bigcup^ u_{i=\ell} P_{(i)}\), \(P_{(i)}=\{x\in P,\;r(x)=i\}\), \(| P_{(i)}|=W_ i\), \(0\leq\ell\leq u\leq r(P)\), and properties \((\ell,u)\)-IS (iff \(\alpha(P_{(\ell,u)})=\max\{W_ \ell,W_ u\})\), \((\ell,u)\)-IC (iff \(\rho(P_{(\ell,u)})=\max\{W_ \ell,W_ u\})\), strong-IS \(((\ell,u)\)-IS for all \(0\leq\ell \leq u\leq r(P))\) and strong-IC \(((\ell,u)\)-IC for all \(0\leq \ell\leq u\leq r(P))\). If \(L_ n(q)\) denotes the poset of subspaces of the \(n\)-dimensional space over the finite field with \(q\) elements and if \(Q_ n\) denotes the face poset of the \(n\)-cube, then it is shown that \(L_ n(q)\) and \(Q_ n\) have the strong IS-property (T3). Next on the list are Peck posets, symmetric chain orders, special symmetric chain orders (strong IC- property) closed under product (of posets) including finite Boolean lattices \(B(n)=C^ n_ 2\), chain products and shuffle posets as defined by Greene. Also, if \(L(m,n)\) denotes the set of \(n\)-vectors \((a_ 1,\dots,a_ n)\) with \(0\leq a_ 1\leq a_ n\leq m\), \(a_ i\in \mathbb{N}\), the natural numbers, for all \(i\), ordered componentwise (as in the product), then \(L(m,n)\) is Peck and \(L(m,3)\) is shown to have the strong IC-property. The authors have provided some interesting results which may well prove useful in future applications or as part of some toolkit for the construction of other arguments and examples not explained or discussed here.