TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1993

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 1993

3-Interval Irreducible Partially Ordered Sets
Zitatschlüssel Report-349-1993
Autor Stefan Felsner
Jahr 1993
Nummer 349
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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).
Typ der Publikation Preprint
Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe