Technical Report 255-1990

Title

Orthogonal Structures in Directed Graphs

Author

Stefan Felsner

Publication

Journal of Combinatorial Theory, Series B, vol. 57, 1993, pp. 309-321

Source

The report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de

Classification

not available

Keywords

not available

Abstract

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 ell 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 ell pathes takes care of the role of ell 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.