Berge's Conjecture on Directed Path Partitions - A Survey <s> 2. <s> Abstract Using linear programming we prove a generalization of Greene and Kleitman's generalization of Dilworth's theorem on the decomposition of a partially ordered set into chains. <s> BIB001 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> 2. <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> 2. <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> 2. <s> This paper exploits and extends results of Edmonds, Cunningham, Cruse and McDiarmid on matroid intersections. Letr 1 andr 2 be rank functions of two matroids defined on the same setE. For everyS ⊂E, letr 12(S) be the largest cardinality of a subset ofS independent in both matroids, 0≦k≦r 12(E)−1. It is shown that, ifc is nonnegative and integral, there is ay: 2 E →Z + which maximizes\(\sum\limits_S {(k - r_{12} (E - S))y(S)} \) and\(\sum\limits_S {(k + 1 - r_{12} (E - S))y(S)} \), subject toy≧0, ∀j∈E,\(\sum\limits_{S \mathrel\backepsilon j} {y(S) \leqq c_j } \). <s> BIB004 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> 2. <s> Abstract The purpose of this note is to prove a theorem on acyclic digraphs, conjectured by Linial (J. Combin. Theory Ser. A, 30 (1981), 331–334), which includes Greene's theorem (J. Combin. Theory Ser. A, 20 (1976), 69–79) on decompositions of a partially ordered set into antichains. <s> BIB005 </s> Berge's Conjecture on Directed Path Partitions - A Survey <s> 2. <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> BIB006
It is easy to prove that the inequality λ k (G) ≤ χ k (G) holds for G transitive and acyclic (i.e. the digraph of a poset).We leave the proof to the reader. Conjecture 3.8 (Linial BIB003 ) Let G be a digraph and k a positive integer. Then For k = 1 Conjecture 3.8 holds by the Gallai-Roy Theorem   . For k ≥ π 1 (G) the Conjecture also trivially holds since λ k (G) = n in this case. If G is acyclic, Hoffman BIB005 and Saks  showed independently that Definition 3.9 (Orthogonality of colourings and k-path systems) A colouring C = {C 1 , C 2 , . . . , C m } and a k-path system P k are orthogonal if every colour class C i in C meets min{|C i |, k} different paths in P k . The natural conjecture extending Berge's Conjecture (Conjecture 2.8) would be: Conjecture 3.10 (False) Let G be a digraph and let k be a positive integer. Then for every koptimal colouring C there exists a k-path system orthogonal to it. This conjecture holds for digraphs of posets. However, it is false for general digraphs by the counterexample in Figure 4 for k = 1 ([4] ). Here no path meets all colours in C. Aharoni, Hartman and Hoffman BIB006 suggested the following alternative to Conjecture 3.10: Conjecture 3.11 (Aharoni, Hartman, Hoffman's conjecture extending Greene's Theorem BIB006 ) Let G be a digraph and let k be a positive integer. Then for every optimal k-path system P k there exists a colouring C orthogonal to it. Conjecture 3.11 holds in the case that k = 1 (by the proof of the Gallai-Roy Theorem), k ≥ π 1 (G), and when G is the digraph of a poset. For acyclic digraphs, Aharoni, Hartman and Hoffman BIB006 proved the following stronger result, the "dual" analogue of Theorem 2.9. Theorem 3.12 (Aharoni, Hartman, Hoffman BIB006 ) Let G be an acyclic digraph, and let k be a positive integer. Then there exists a colouring C orthogonal to every optimal k-path system P k . The proof of Theorem 3.12 uses a linear programming technique. An alternative constructive proof is described in  . In  , Conjecture 3.11 was proved in the special case where an optimal k-path system contains some path of cardinality one. This result was used to prove Conjecture 3.11 for all bipartite digraphs. In addition, Hartman, Saleh and Hershkowitz  proved Conjecture 3.11 for all orientations of split 1 graphs. We have seen, so far, various concepts, theorems, and conjectures related to two different worlds: on the one hand, the world of path partitions and k-colourings described in Section 2, and on the other hand, the "dual" world of colourings and k-path systems, described in Section 3. There seems to be little connection between these worlds, just as there is no apparent connection between the Gallai-Milgram Theorem (Theorem 1.1) and the Gallai-Roy Theorem (Theorem 3.4), (except for the common author Gallai ). However, there is a tight connection between a path partition and an orthogonal k-colouring on the one hand, and a k-path system and an orthogonal colouring on the other hand, as is evident in the next theorem: Theorem 3.13 (B.-A. Hartman  ) Let P be a path partition, and C k a k-colouring. Then P and C k are orthogonal if and only if the h-path defined by P h = P + , and the associated colouring For posets, Greene  proved a tight connection between the parameters λ i and α i . Let ∆ i = λ i − λ i−1 , and δ j = α j − α j−1 for i = 1, 2, . . . , α and j = 1, 2, . . . , λ, where λ 0 = α 0 = 0. Theorem 3.14 (Greene's Theorem on conjugate partitions  ) In digraphs of posets, the sequences ∆ = {∆ i } and δ = {δ i } are monotone decreasing and form conjugate partitions 2 of the number n, for each h = 1, 2, . . . , λ. Theorem 3.14 does not extend to acyclic digraphs. However, if we denote ∆ * j = π j − π j−1 , where π 0 = 0, j = 1, 2, . . . , λ, then we have: is the union of two disjoint sets X and Y , where X is a clique and Y is an independent set. 2 that is, δ h equals the number of parts in ∆ of size at least h Theorem 3.15 (B.-A. Hartman  ) In acyclic digraphs the sequences {∆ i }, i = 1, . . . , π 1 , and {∆ * j }, j = 1, . . . , λ, are monotone decreasing and form conjugate partitions of the number n. Frank BIB002 presented an elegant way to derive together both the Greene-Kleitman Theorem 2.3 and Greene's Theorem 3.6, using network flow techniques, as discussed in section 2.2.3. Aharoni and Hartman generalized Frank's theorem to all acyclic digraphs in the following way: Theorem 3.16 (B.-A. Hartman  ) Let G be an acyclic digraph. Then there exists a sequence where each P j is a path partition of G and each C i is an i-colouring satisfying: 1. Any member of the sequence (whether P j or C i ) is orthogonal to the last member of other type preceding it; 2. If P j and C i are orthogonal (where P j and C i are in the sequence), then P j is i-optimal; and 3. |P The following corollaries are extensions of other theorems of Greene  to acyclic digraphs. (See also Saks  , Groflin and Hoffman BIB004 and Hoffman and Schwartz BIB001 for other extensions ).