Antichain cutsets (Q762182)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Antichain cutsets
scientific article

    Statements

    Antichain cutsets (English)
    0 references
    0 references
    0 references
    0 references
    1985
    0 references
    If P is a poset, then a cutset A of P meets every maximal chain of P. Those finite posets which can be expressed as unions of antichain cutsets have a reasonably non-chaotic appearance. In this paper the authors prove a theorem similar in spirit to the classification theorem of modular (or non-modular) lattices, viz., T1: A poset in which every chain is finite is the union of antichain cutsets iff it contains no alternating-cover cycle. The theorem is a consequence of T2: In a poset in which every chain is finite, an element x is contained in an anti-chain cubset iff there is no generalized alternating-cover cycle based at x. Given P, a sequence \(\{x=x_ 0,x_ 1,...,x_ n=y\}\) is a generalized alternating-cover path from x to y provided \(x_ i<x_{i+1}\) whenever i is even and \(x_ i>x_{i+1}\) whenever i is odd. If \(y=x\) and n is odd the sequence is a generalized alternating-cover cycle based at x. If in addition \(x_{2u}=x_{2v+1}\) implies \(2u=0\), \(2v+1=n\), then the generalized alternating-cover cycle is an alternating-cover cycle. Additional information is also obtained. Thus, if \(N=\{a<b>c<d\}\) then T3: If P is a poset which contains no subset isomorphic to N, then every finite minimal cutset of P is an antichain. Also T4: The only antichain cutsets in \(2^ n\) are the levels. This interesting paper is one more indication of the strong relationship that exists between chains and antichains in posets, a relationship that can also be made meaningful in a functorial setting.
    0 references
    forbidden substructures
    0 references
    finite posets
    0 references
    unions of antichain cutsets
    0 references
    alternating-cover cycle
    0 references
    levels
    0 references
    chains
    0 references
    antichains
    0 references

    Identifiers