TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1993

COGA 5-Wheel

Page Content

to Navigation

Preprints 1993

3-Interval Irreducible Partially Ordered Sets
Citation key Report-349-1993
Author Stefan Felsner
Year 1993
Number 349
Institution Technische Universität Berlin, Institut für Mathematik
Abstract In this paper we discuss the characterization problem for posets of interval dimension at most 2. That is, we attempt to compile the minimal list of forbidden posets for interval dimension 2. Members of this list are called 3-interval irreducible posets. The problem is related to a series of characterization problems which have been solved earlier. These are: The characterization of planar lattices, due to Kelly and Rival, the characterization of posets of dimension at most 2 (3-irreducible posets) which has been obtained independently by Trotter and Moore and by Kelly and the characterization of bipartite 3-interval irreducible posets due to Trotter. We show that every 3-interval irreducible poset is a reduced partial stack of some bipartite 3-interval irreducible poset. Moreover, we succeed in classifying the 3-interval irreducible partial stacks of most of the bipartite 3-interval irreducible posets. Our arguments depend on a transformation $P \to B(P)$, such that $\dim\: P = \dim\: B(P)$. This transformation has been introduced by Felsner, Habib and Möhring (see \citeReport-285-1991).
Bibtex Type of Publication Preprint
Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe