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
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