ISSN:
1572-9273
Schlagwort(e):
Primary 06A07
;
secondary 05C70
;
Partial order
;
interval
;
stability
;
covering
;
Sperner property
;
symmetric chains
;
NP-completeness
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
Notizen:
Abstract Given a finite ranked posetP, let α(P) be the maximum size of a subset ofP such that no two elements of it belong simultaneously to some interval ofP and let ϱ(P) be the minimum number of intervals covering all elements ofP. We say thatP has the strong interval stability property (resp. the strong interval covering property) if for each subposetP′ induced by consecutive levels ofP, i.e.,P′=P (l)∪...∪P (u), one has α(P′)=max{|P (l)|, |P (u)|} (resp. ϱ(P′)=max{|P (l)|, |P (u)|}). We prove these properties for several classes of posets and discuss some general facts concerning the numbers α(P) and ϱ(P), e.g., NP-completeness and min-max relations.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF00814408
