On the n-cutset property (Q1264162)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the n-cutset property |
scientific article |
Statements
On the n-cutset property (English)
0 references
1989
0 references
Let P be a (finite) partially ordered set, \(x\in P\). A subset S of P is called a cutset for x in P if every element in S is noncomparable with x and every maximal chain of P meets \(S\cup \{x\}\). Let c(P) denote the smallest integer k such that every element \(x\in P\) has a cutset S with \(| S| \leq k\). If c(P)\(\leq n\), then we say that P has the n-cutset property. The author studies the following problem: Given P, what is the smallest n such that P can be embedded in a partially ordered set having the n-cutset property? He characterizes, by means of forbidden configurations, those P which can be embedded in a partially ordered set having the 1-cutset property. Let \(2^ n\) denote the Boolean lattice with n generators and let \(B_ n\) be the set of all atoms and dual atoms of \(2^ n\). The author finds a lower bound of c(P) for P containing a copy of \(2^ n\), and proves that for \(n>3\) there is a partially ordered set containing \(2^ n\) with \(c(P)<c(2^ n)\). He also proves that for every positive integer n there is an integer N such that, if \(B_ m\) is contained in a poset having the n-cutset property, then \(m\leq N\).
0 references
partially ordered set
0 references
chain
0 references
n-cutset property
0 references
forbidden configurations
0 references
Boolean lattice
0 references