Another Note on Dilworth's Decomposition Theorem

This paper proposes a new proof of Dilworth's theorem. The proof is based upon the minflow/maxcut property in flow networks. In relation to this proof, a new method to find both a Dilworth decomposition and a maximal antichain is presented. 1. Introduction Several proofs are known for Dilworth's theorem. This theorem says that, in a poset , a maximal antichain and a minimal path cover have equal size. Shortly after Dilworth's seminal paper [1] a “Note” [2] was published containing an algorithmic proof, that is, a proof which also gives a method to find a combination of a maximal antichain and a minimal path cover. The other proofs [1, 3–5] are nonalgorithmic. The key issue in [2] is the relation between a minimal path cover and a maximal antichain in on the one hand and a maximal matching and a minimal vertex cover (in this order) in an associated bipartite graph on the other hand. Dilworth's theorem is proved in [2] using K？nig's theorem stating that, in a bipartite graph, a maximal matching and a minimal vertex cover have equal size. The combination of a maximal matching and a minimal vertex cover in corresponds to a maxflow/mincut combination in a flow network akin to . So the obvious algorithm for a minimal path cover along with a maximal antichain is executing a maxflow/mincut algorithm in associated indirectly to . In the current paper a shortcut is proposed between maxflow/mincut and an optimal path cover jointly with an antichain. To a given poset we associate a flow network which is much simpler than graph constructed via a matching/vertex cover instance. A similar idea for finding a maximal antichain is found in [6]. However, the discussion in that paper was not connected with Dilworth's theorem. Other more complex algorithms in this domain can be found in [7–10]. For an application of the maximal antichain we refer to [11, 12]. 2. Some Preliminaries A poset is a partially ordered set , where denotes a transitive order relation. An ordered pair with is called transitive if there exists an element such that . A poset can be transformed into a directed acyclic graph in a straightforward manner. Each nontransitive pair with generates an arc . An example of a graph derived from a poset is given in Figure 1. Figure 1: A directed acyclic graph (DAG). An antichain in a directed acyclic graph is a set of nodes, no two of which are included in any path of . A path cover in is a collection of paths, not necessarily disjoint, such that every node is included in at least one path. The number of paths is called the size of the path cover. Now we can