Berge's Conjecture on Directed Path Partitions - A Survey <s> 2.2.3 <s> Abstract If P is a partially ordered set, a k-family of P is a subset which contains no chains of length k + 1. This paper examines the structure of the set of k-families of P. An extension of Dilworth's theorem is obtained by relating the maximum size of a k-family to certain partitions of P into chains. A natural lattice ordering on k-families is defined and analyzed, and a number of strong intersection properties are obtained. Finally, the k-families of P are used to define a class of submodular set functions on P, which can be used to generalize a number of results in transversal theory. <s> BIB001 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> 2.2.3 <s> Abstract A common generalization of the theorems of Greene and Greene and Kleitman is presented. This yields some insight into the relation of optimal chain and antichain families of a partially ordered set. The fundamental device is the minimal cost flow algorithm of Ford and Fulkerson. <s> BIB002
Network Flows and Bipartite Graphs. In BIB002 , Frank proves the Greene-Kleitman Theorem BIB001 and Greene's Theorem  (see section 3) using network flows. Frank uses an algorithm of Ford and Fulkerson  for the following problem: Let N = (V, E) be a network with two specified vertices: a source s and a sink t. Let a(x, y) be a non-negative integral cost, and let c(x, y) be a positive integral capacity assigned to each edge (x, y). The algorithm of Ford and Fulkerson  finds a minimum cost flow from s to t, having a value v given in advance. The algorithm invokes dual variables π(x) assigned to the vertices of G. This so-called potential function π is non-negative integer valued, and π(s) = 0 throughout the process. The current π(t) = p is called the potential value. We do not go into the details here of how the network is constructed using the given digraph. However, we will state that the flow from s to t corresponds to a path partition in G, and, similar to the LP technique, the orthogonal k-colouring is constructed using the potential function π(x), with potential value p = k. The algorithm proceeds in stages. Initially, v = 1 and p = k = 1. At each stage, either the value of the flow v is increased, in which case the p-norm of the current path partition improves, or the potential value p (i.e. k) increases by one, thus allowing more edges in the current network to be admissible for the next stage. Frank's algorithm is applied only to digraphs of posets, and it supplies a constructive proof of the theorems by Greene and Kleitman (Theorem 2.3) and Greene (Theorem 3.6 in Section 3). Aharoni and Hartman [1] used Frank's ideas to generalize his algorithm to acyclic digraphs, and in the case that P = P + , for all digraphs. They preferred to use standard techniques in bipartite graphs, rather than Ford and Fulkerson's algorithm for minimum cost flow of a given value. We will demonstrate below some of their ideas and proof techniques, which are very intuitive, and use basic notions of matchings and alternating paths in bipartite graphs. Let G = (V, E) be a directed graph. We associate with G an undirected bipartite graph G = (V , E) as follows: The edge set E is defined by Figure 2 , for an example).