direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 1990

Orthogonal Structures in Directed Graphs
Zitatschlüssel Report-255-1990
Autor Stefan Felsner
Seiten 309-321
Jahr 1990
Journal Journal of Combinatorial Theory, Series B, 1993
Jahrgang 57
Nummer 255
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Using the minimal cost flow algorithm of Ford and Fulkerson and the notion of orthogonality between chain and antichain families András Frank could give common access (and proof) to some famous results in the theory of finite posets: 1.\ Theorem of Greene and Kleitman, 2.\ Theorem of Greene, 3.\ the $t$-phenomenon, 4.\ the conjugacy of the partitions associated with the $k$ antichain and ℓ chain families. Some new insight into the behaviour of the minimum cost flow algorithm on the special networks associated with posets and digraphs enables us to exhibit orthogonal structures in arbitrary digraphs. The role of $k$ antichain families is taken by families of $k$ disjoint $1$–weightings, a family of disjoint pathes and cycles including ℓ pathes takes care of the role of ℓ chain families. We then show how the orthogonal structures can be used to generalize the Greene Kleitman theory to acyclic directed graphs and partly even to arbitrary directed graphs.
Typ der Publikation Preprint
Download Bibtex Eintrag