On the n-cutset property (Q1264162)

From MaRDI portal
Revision as of 18:41, 17 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    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

    Identifiers