Effective constructions of cutsets for finite and infinite ordered sets (Q3765826)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4023345
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Effective constructions of cutsets for finite and infinite ordered sets |
scientific article; zbMATH DE number 4023345 |
Statements
1987
0 references
forbidden substructures
0 references
alternating cover cycle
0 references
algorithm
0 references
antichain cutsets
0 references
polynomial complexity
0 references
regular poset
0 references
chain condition
0 references
minimal cutsets
0 references
generalized N
0 references
finite posets
0 references
0.8603803515434265
0 references
0.8463658690452576
0 references
0.8389591574668884
0 references
Effective constructions of cutsets for finite and infinite ordered sets (English)
0 references
It is a well-known result of the authors of this paper that an element x of a finite poset is contained in an antichain cutset if and only if it is not contained in a (generalized) alternating cover cycle. The authors provide several interesting improvements and expansions of this result. First, based on two important technical lemmas, they are able to replace an apparent elegant exponential time (step) algorithm for the construction of antichain cutsets by one of polynomial complexity. Second, they are able to add to the store of general poset results by dropping the requirement that posets be finite in carefully controlled circumstances and so give extensions and improvements of other results via: Theorem 2: a regular poset satisfying a chain condition is the union of minimal cutsets; Theorem 3: in a regular poset satisfying a chain condition every minimal cutset is an antichain if and only if P contains no subset isomorphic to N; and Theorem 4: in a poset every maximal antichain meets every maximal chain iff it contains no generalized N as a subdiagram. Infinite poset theory will benefit from many other successful adaptations of arguments first made for finite posets, while in the theory of finite posets reduction of arguments to the most effective possible will also continue to be an active and important area of research. In this paper the authors give a very nice illustration of contributions to both trends at once.
0 references