The interval inclusion number of a partially ordered set (Q1176729)

From MaRDI portal
Revision as of 09:59, 15 May 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
The interval inclusion number of a partially ordered set
scientific article

    Statements

    The interval inclusion number of a partially ordered set (English)
    0 references
    0 references
    0 references
    25 June 1992
    0 references
    Für eine beliebige teilweise geordnete Menge \(P\) betrachten die Verfasser eine Funktion \(f\), so daß \(f(x)\) für jedes \(x\in P\) eine Menge ist und \(\{f(x):x\in P\}\), geordnet durch \(\subset\), mit \(P\) isomorph ist. Besondere Aufmerksamkeit wird dem Fall gewidmet, wenn \(f(x)\) für jedes \(x\in P\) Vereinigung einer endlichen Anzahl von Intervallen auf der reellen Zahlengeraden \(\mathbb{R}\) ist. Durch \(i(P)\) wird die minimale Anzahl \(k\) bezeichnet, so daß es ein \(f\) gibt, für das jedes \(f(x)\) höchstens \(k\) Intervalle enthält. Außerdem wird durch \(\dim(P)\) die minimale Anzahl der linear geordneten Mengen \(I_ i\) bezeichnet, so daß jedes \(I_ i\) dieselben Elemente wie \(P\) hat, aber dabei die Ordnung von \(P\) in \(I_ i\) zu einer linearen Ordnung ergänzt worden ist, wobei die Ordnung in \(P\) der Durchschnitt der Ordnungen in allen \(I_ i\) ist. Es werden folgende Resultate bewiesen: Für jedes \(P\) gilt \(i(P)\leq[\dim(P)/2]\), wobei es für jedes \(k\) ein \(P\) gibt, so daß \(\dim(P)=2k+1\) und \(i(P)=k\). Wenn \(P^*\) die duale Ordnung von \(P\) ist, dann gilt \(i(P)-1\leq i(P^*)\leq i(P)+1\). Wenn für teilweise geordnete Mengen \(P\) und \(Q\) die Menge \(P\times Q\) komponentenweise geordnet ist, dann gilt \(i(P\times Q)\leq i(P)+i(Q)\). Für die Boolesche Algebra \(B_ n\) mit \(n\) Elementen gilt \(i(B_ n)\leq [n/2]\). Wenn \(P-x\) die Menge \(P\) ohne Element \(x\) ist, dann gilt \(i(P-x)\geq i(P)/2\), für maximales oder minimales \(x\) aber \(i(P-x)\geq i(P)-1\). Falls 1 bzw. 0 zu \(P\) als größtes bzw. kleinstes Element hinzugefügt ist, so gilt \(i(P\cup\{1\})=i(P)\) bzw. \(i(P\cup\{0\})\leq i(P)+1\).
    0 references
    linearly ordered set
    0 references
    Boolean algebra
    0 references
    interval inclusion number
    0 references
    0 references

    Identifiers