Abstract
Given a poset P = (X, ≺ ), a partition X 1, ..., X k of X is called an ordered partition of P if, whenever x ∈ X i and y ∈ X j with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, \(m/k - c(k)\sqrt{m}\), for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Edwards, C.S.: Some extremal properties of bipartite subgraphs. Can. J. Math. 25, 475–485 (1973)
Edwards, C.S.: An improved lower bound for the number of edges in a largest bipartite subgraph. In: Recent Advances in Graph Theory (Proc. Second Czechoslovak Sympos., Prague, 1974), pp. 167–181. Academia, Prague (1975)
Garey, M.R., Johnson, D.S.: Computers and Intractability—A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)
Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169–197 (1981)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, 2nd edn. Springer-Verlag, Berlin (1993)
Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Oxford University Press, Oxford (1979)
Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4), 761–777 (2001)
Saks, M.: A short proof of the existence of k-saturated partitions of partially ordered sets. Adv. Math. 33(3), 207–211 (1979)
Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80(2), 346–355 (2000)
Scott, A.: Judicious partitions and related problems. In: Surveys in Combinatorics 2005, pp. 95–117. Cambridge University Press, Cambridge (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by an EPSRC doctoral training grant.
Rights and permissions
About this article
Cite this article
Patel, V. Partitioning Posets. Order 25, 131–152 (2008). https://doi.org/10.1007/s11083-008-9085-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-008-9085-5