A length-width inequality for partially ordered sets with two-element cutsets (Q1124616): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0095-8956(89)90044-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1996427104 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Compact Spaces and Spaces of Maximal Complete Subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The length, the width and the cutset-number of finite ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Antichains and Finite Sets that Meet all Maximal Chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite cutsets and finite antichains / rank | |||
Normal rank |
Latest revision as of 10:26, 20 June 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