A length-width inequality for partially ordered sets with two-element cutsets (Q1124616): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:16, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A length-width inequality for partially ordered sets with two-element cutsets |
scientific article |
Statements
A length-width inequality for partially ordered sets with two-element cutsets (English)
0 references
1989
0 references
Let P be a finite poset and \(x\in P\). A cutset for x is each set \(C\subseteq P\) such that (i) \(x\| C\) (that is, x is noncomparable with a for \(a\in C)\) and (ii) every maximal chain in P intersects \(C\cup \{x\}\). A poset P has the m-cutset property if every element of P has a cutset with at most m elements. Let w(P) denote the width of the poset P and let \(\ell (P)\) denote the number of elements of the largest chain in P. The connections between w(P) and \(\ell (P)\) are studied in the paper. It is proved (Theorem 1) that if P is a finite poset with the 2-cutset property, then \(\ell (P)\geq w(P)-2\), and that this result is best possible. A similar inequality is also given for posets with the m-cutset property for \(m>2\).
0 references
finite poset
0 references
m-cutset property
0 references
width
0 references
largest chain
0 references
2-cutset property
0 references