Berge's Conjecture on Directed Path Partitions - A Survey <s> Introduction and definitions <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> Introduction and definitions <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 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> Introduction and definitions <s> The celebrated Dilworth theorem (Ann. of Math. 51 (1950), 161–166) on the decomposition of finite posets was extended by Greene and Kleitman (J. Combin. Theory Ser. A 20 (1976), 41–68). Using the Gallai-Milgram theorem (Acta Sci. Math. 21 (1960), 181–186) we prove a theorem on acyclic digraphs which contains the Greene-Kleitman theorem. The method of proof is derived from M. Saks' elegant proof (Adv. in Math. 33 (1979), 207–211) of the Greene-Kleitman theorem. <s> BIB003 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> Introduction and definitions <s> Let G be an acyclic directed graph with \V(G)\>k. We prove that there exists a colouring { Cx, C2,..., Cm } such that for every collection {Pl9 P2,... ,Pk} of k vertex disjoint paths with |UjLi Pj\ a maximum, each colour class C, meets min{|CJ, k} of these paths. An analogous theorem, partially interchanging the roles of paths and colour classes, has been shown by Cameron [4] and Saks [17] and we indicate a third proof. <s> BIB004
Dilworth's Theorem (Theorem 1.2) was generalised by Greene and Kleitman BIB001 by considering a set of k disjoint independent sets (1 ≤ k ≤ n),(or antichains) instead of one independent set (antichain). . . , C k } of k disjoint independent sets called colour classes. (Some of the colour classes may be empty). The cardinality of a k-colouring |C i | and C k is said to be optimal if |C k | is as large as possible. Denote by α k (G) the cardinality of an optimal k-colouring in G. Berge  called a k-colouring a partial k-colouring, because it is, in fact, a partial colouring of the vertices of a graph using k colours. We prefer the shorter name k-colouring. In the cases of Theorems 1.1 and 1.2 we considered path partitions with a minimum number of paths. We need here an extension of this norm. Definition 2.2 (k-norm of a path partition) For each positive integer k, the k-norm |P| k of a path partition P = {P 1 , P 2 , . . . , P m } is defined by A partition which minimizes |P| k is called k-optimal. Denote by π k (G) the k-norm of a k-optimal path partition in G. Note that a 1-optimal path partition is a partition that contains a minimum number of paths, and π 1 (G) = π(G). Denote by P + the set of paths in P of cardinality more than k, (which we also call long paths), and by P 0 the set of paths in P of cardinality at most k, (called short paths). For a set of vertex disjoint paths P, we write V [P] = {V (P ); P ∈ P}. Now Definition 2.2 can be alternatively written as We are now able to state the Greene-Kleitman Theorem: Theorem 2.3 (Greene-Kleitman Theorem BIB001 ) Let G be a digraph of a poset, and let k be a positive integer. Then α k (G) = π k (G). Observation 2.4 1. For k = 1, Theorem 2.3 is identical to Dilworth's theorem (Theorem 1.2). 2. If G is transitive and, hence, acyclic (i.e. a digraph of a poset), then it is trivial to prove that Observation 2.4-2 follows from the fact that each path P i meets any k-colouring in at most min{|P i |, k} vertices (since a colour class and a path (i.e. a clique), can meet by at most one vertex). Hence, for any k-colouring C k = {C 1 , C 2 , . . . , C k } and any path partition P = {P 1 , P 2 , . . . , P m } we have: (The first equality follows from the fact that a path partition partitions the vertex set of a graph into disjoint sets.) In particular, if we take an optimal k-colouring and a k-optimal path partition then we obtain ¿From Observation 2, together with Theorem 2.3, we conclude: Corollary 2.5 Let G be a digraph of a poset, k a positive integer, P a k-optimal path partition, and C k an optimal k-colouring. Then C k meets every path in P in exactly min{|P i |, k} vertices. If G is not a graph of a poset, then a colour class (or a k-colouring) may meet a path P more than once (more than k times), thus, it is possible that the opposite inequality holds in Equation 1. Linial BIB003 conjectured the following extension of the Greene-Kleitman Theorem to all digraphs: Conjecture 2.6 (Linial BIB003 ) Let G be a digraph and k a positive integer. Then Conjecture 2.6 can be referred to as the "weak path partition conjecture". Berge was intrigued by the relationship between k-optimal path partitions and optimal k-colourings as reflected in Corollary 2.5. The following definitions captures this special relationship: Definition 2.7 (Orthogonality of path partitions and k-colourings) A k-colouring C k is orthogonal to a path partition P = {P 1 , P 2 , . . . , P m } if C k meets every path in P in min{|P i |, k} different colour classes. Clearly, the maximum number of colours that a path P can meet a k-colouring is min{|P |, k}. Berge  used a different term for orthogonality, defining a k-colouring C k to be strong for a path P if C k meets P in exactly min{|P |, k} different colour classes. We prefer the concept of orthogonality as used in BIB002 and BIB004 . We are now ready to state Berge's conjecture extending the Greene-Kleitman Theorem, a conjecture which is still open today. Conjecture 2.8 (Berge's strong path partition conjecture  ) Let G be a digraph and let k be a positive integer. Then for every k-optimal path partition P there exists a k-colouring orthogonal to it. Conjecture 2.8 implies Conjecture 2.6 as follows: Let P be a k-optimal path partition and let C k be a k-colouring orthogonal to it. Then Berge observed in  that Conjecture 2.8 holds in the following special cases: 1. For k = 1, by Theorem 1.4. 2. In the case that the k-optimal path partition contains only short paths, i.e. paths of cardinality at most k. This implies that the conjecture also holds for k ≥ λ. 3. For digraphs containing a Hamilton path P 0 . In this case P = {P 0 } is a k-optimal path partition with P| k = k, and any k-colouring with no empty colour classes is orthogonal to it.