Semiantichains and Unichain Coverings in Direct Products of Partial Orders.

Abstract

We conjecture a generalization of Dilworth's theorem to direct products of partial orders. In particular, we conjecture that the largest 'semiantichain' and the smallest 'unichain covering' have the same size. We consider a special class of semiantichains and unichain coverings and determine when equality holds for them. This conjecture implies the existence of k-saturated partitions. A stronger conjecture, for which we also prove a special case, implies the Greene-Kleitman result on simultaneous k and (k+1)-saturated partitions. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1980
Accession Number
ADA092256

Entities

People

  • Craig A. Tovey
  • Douglas B. West

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Boolean Algebra
  • Classification
  • Combinatorial Analysis
  • Computer Programming
  • Computer Science
  • Inequalities
  • Integer Programming
  • Integrals
  • Mathematics
  • Military Research
  • Operations Research
  • Saturation
  • Security
  • Sequences
  • Two Dimensional
  • Universities

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.