Interval stability and interval covering property in finite posets (Q1803666): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Joseph Neggers / rank | |||
Property / reviewed by | |||
Property / reviewed by: Joseph Neggers / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3050437 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5668821 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5805073 / 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: Q3797242 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Posets of shuffles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sufficient Conditions for a Symmetric Chain Order / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A partition of L(3,n) into saturated symmetric chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Boolesche Minimalpolynome und Überdeckungsprobleme / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3196862 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3202956 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A symmetric chain decomposition of L(4,n) / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 17:53, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Interval stability and interval covering property in finite posets |
scientific article |
Statements
Interval stability and interval covering property in finite posets (English)
0 references
29 June 1993
0 references
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.
0 references
interval covering
0 references
interval stability
0 references
Sperner property
0 references
NP-completeness
0 references
Peck posets
0 references
symmetric chain orders
0 references
chain products
0 references
shuffle posets
0 references