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=\{ac<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.
- A decomposition theorem for partially ordered sets
- Compact Spaces and Spaces of Maximal Complete Subgraphs
- Finite cutsets and finite antichains
- Graphs indecomposable with respect to the X-join
- scientific article; zbMATH DE number 3914376 (Why is no real title available?)
- Maximal chains and antichains
- The Recognition of Series Parallel Digraphs
- A companion to Grillet's theorem on maximal chains and antichains
- Chaines alternées. (Alternating chains)
- Ladders in ordered sets
- Cutsets of Boolean lattices
- Chains, antichains, and fibres
- A chain decomposition theorem
- Maximal chains and cutsets of an ordered set: A Menger type approach
- The Menger property for infinite ordered sets
- The jump number of Z-free ordered sets
- Search and sweep numbers of finite directed acyclic graphs
- Orbits of antichains in ranked posets
- On the n-cutset property
- Minimum cutsets for an element of a Boolean lattice
- Every cutset meets every fibre in certain poset products
- On the dimension of ordered sets with the 2-cutset property
- Obituary: Ivan Rival
- A note on operators of deletion and contraction for antichains
- Antichain cutsets of strongly connected posets
- Inversions, cuts, and orientations
- Orders with level diagrams
- Chain blockers and convoluted Catalan numbers
- Finite antichain cutsets in posets
- scientific article; zbMATH DE number 4162946 (Why is no real title available?)
- scientific article; zbMATH DE number 4023345 (Why is no real title available?)
- scientific article; zbMATH DE number 1153451 (Why is no real title available?)
- Cycle-free cuts of mutual rank probability relations.
- Antichain Simplices
- The PT-order, minimal cutsets and Menger property
- Remarks on antichains in the causality order of space-time
- Finite cutsets and finite antichains
- The lattice of antichain cutsets of a partially ordered set
- Wide posets with fixed height and cutset number
- Diagrams, orientations, and varieties
This page was built for publication: Antichain cutsets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q762182)
