Abstract
Consider the partition of a set of integers into parts. Various partition properties have been proposed in the literature to facilitate the restriction of the focus of attention to some small class of partitions. Recently, Hwang, Rothblum and Yao defined and studied the sortability of these partition properties as a tool to prove the existence of a partition with such a property in a given family. In this paper we determine the sortability indices of the seven most interesting properties of partitions providing a complete solution to the sortability issue.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. Anily and A. Federgruen, “Structured partitioning problems,” Oper. Res., vol. 39, pp. 130–149, 1991.
E.R. Barnes, A.J. Hoffman, and U.G. Rothblum, “On optimal partitions having disjoint convex and conic hulls,” Math. Programming, vol. 54, pp. 69–86, 1991.
A.K. Chakravarty, J.B. Orlin, and U.G. Rothblum, “Consecutive optimizers for a partitioning problem with applications to optimal inventory grouping for joint replenishment,” Oper. Res. vol. 33, pp. 820–834, 1985.
S. Gal and B. Klots, “Optimal partitioning which maximizes the sum of the weighted averages,” Oper. Res., vol. 43, pp. 500–508, 1995.
F.K. Hwang and C.L. Mallows, “Enumerating consecutive and nested partitions,” J. Combin. Theory, Series A, vol. 70, pp. 323–333, 1995.
F.K. Hwang, J. Sun, and E.Y. Yao, “Optimal set partitioning,” SIAM J. Alg. and Disc. Meth., vol. 6, pp. 163–170, 1985.
F.K. Hwang, U. G. Rothblum, and Y.C. Yao, “Localizing combinatorial properties of partitions,” Disc. Math, vol. 160, pp. 1–23, 1996.
G. Kreweras, “Sur les partitions non croisees d'un cycle,” Disc. Math, vol. 1, pp. 333–350, 1972.
S.C. Liao, H.G. Yeh, F.K. Hwang, and G.J. Chang, “A simple and direct derivation for the number of noncrossing partitions,” Proc. AMS, vol. 126, pp. 1579–1581, 1998.
H.G. Yeh, S.C. Liao, F.K. Hwang, and G.J. Chang, “Enumerating partitions with given part-sizes,” Bull. Inst. Math., Academia Sinica, vol. 26, pp. 33–38, 1998.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Chang, G.J., Chen, FL., Huang, L. et al. Sortabilities of Partition Properties. Journal of Combinatorial Optimization 2, 413–427 (1998). https://doi.org/10.1023/A:1009737108224
Issue Date:
DOI: https://doi.org/10.1023/A:1009737108224