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

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

      Identifiers

      0 references
      0 references
      0 references
      0 references