Number of vertices of the polytope of integer partitions and factorization of the partitioned number. (English) Zbl 1530.05012
Let \(P(n)\) denote the set of integer partitions of \(n\), and let \(P_n\) be the convex hull of \(P(n)\), which is named as the polytope of partitions of \(n\). The main object of interest in this paper under review is \(v(n)\), the number of vertices in the polytope \(P_n\). By utilizing a counting formula due to N. Metropolis and P. R. Stein [J. Comb. Theory 9, 365–376 (1970; Zbl 0206.02001)] for partitions of \(2n\) that can be split as two partitions of \(n\), the author shows that the plot of \(v(n)\) has a tooth-shaped form with the highest peaks at primes. The author also considers other properties satisfied by \(v(n)\), and offers a number of interesting conjectures. Insights with regard to the master corner polyhedron on the cyclic group are also raised.
Reviewer: Shane Chern (University Park)
Citations:
Zbl 0206.02001Online Encyclopedia of Integer Sequences:
a(n) is the number of partitions of 2n that can be obtained by adding together two (not necessarily distinct) partitions of n.Number of knapsack partitions of n.
Number of vertices of the integer partition polytope.
Number of vertices of the master corner polyhedron on the cyclic group of order n + 1.
References:
| [1] | Andrews, G. E., The Theory of Partitions (Encyclopedia of Mathematics and Its Applications, 2). (1976), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0371.10001 |
| [2] | Anonymous (joriki), Number of partitions of 2n with no element greater than n. |
| [3] | Breuer, F.; Eichhorn, D.; Kronholm, B., Polyhedral geometry, supercranks, and combinatorial witnesses of congruences for partitions into three parts, Eur. J. Combinat, 65, 230-252 (2017) · Zbl 1369.05020 |
| [4] | Carathéodory, C., Über den Variabilitätsbereich der Fourier’schen Konstanten von positiven harmonischen Funktionen, Rendiconti del Circolo Matematico di Palermo, 32, 193-217 (1911) · JFM 42.0429.01 · doi:10.1007/BF03014795 |
| [5] | Ehrenborg, R.; Readdy, M. A., The Möbius function of partitions with restricted block sizes, Adv. Appl. Math, 39, 283-292 (2007) · Zbl 1129.05005 · doi:10.1016/j.aam.2006.08.006 |
| [6] | Engel, K.; Radzik, T.; Schlage-Puchta, J.-C., Optimal integer partitions, Eur. J. Combinat, 36, 425-436 (2014) · Zbl 1284.05028 · doi:10.1016/j.ejc.2013.09.004 |
| [7] | Gomory, R. E., Some polyhedra related to combinatorial problems, Linear Algebra Appl, 2, 451-558 (1969) · Zbl 0184.23103 · doi:10.1016/0024-3795(69)90017-2 |
| [8] | Gomory, R. E., The atoms of integer programming, Ann. Oper. Res, 149, 99-102 (2007) · Zbl 1213.90020 · doi:10.1007/s10479-006-0110-z |
| [9] | Konvalinka, M.; Pak, I., Cayley compositions, partitions, polytopes, and geometric bijections, J. Combinat. Theory. Ser. A, 123, 86-91 (2014) · Zbl 1281.05015 |
| [10] | Mano, S., Partition structure and the A-hypergeometric distribution associated with the rational normal curve, Electron. J. Stat, 11, 4452-4487 (2017) · Zbl 1382.62005 |
| [11] | Metropolis, N.; Stein, P. R., An elementary solution to a problem in restricted partitions, J. Combinat. Theory, 9, 365-376 (1970) · Zbl 0206.02001 · doi:10.1016/S0021-9800(70)80091-6 |
| [12] | Olsen, MC.; Hibi, T.; Tsuchiya, A., Algebraic and Geometric Combinatorics on Lattice Polytopes. Proceedings of the Summer Workshop on Lattice Polytopes, Polyhedral geometry for lecture hall partitions, 330-353 (2019), Singapore: World Scientific, Singapore · Zbl 1418.14001 |
| [13] | Onn, S.; Shlyk, V. A., Some efficiently solvable problems over integer partition polytopes, Discret. Appl. Math, 180, 135-140 (2015) · Zbl 1303.05012 · doi:10.1016/j.dam.2014.08.015 |
| [14] | Reznik, B., Lattice point simplices, Discret. Math, 60, 219-242 (1986) · Zbl 0593.52008 |
| [15] | Savage, C. D., The mathematics of lecture hall partitions, J. Combinat. Theory. Ser. A, 144, 443-475 (2016) · Zbl 1343.05032 · doi:10.1016/j.jcta.2016.06.006 |
| [16] | Shlyk, V. A., Polytopes of partitions of numbers, Eur. J. Combinat, 26, 1139-1153 (2005) · Zbl 1114.52010 · doi:10.1016/j.ejc.2004.08.004 |
| [17] | Shlyk, V. A., On the vertices of the polytopes of partitions of numbers, Doklady Natsional’noi Akademii Nauk Belarusi, 52, 5-10 (2008) · Zbl 1260.52010 |
| [18] | Shlyk, V. A., Integer partitions from the polyhedral point of view, Electron. Notes Discret. Math, 43, 319-327 (2013) · doi:10.1016/j.endm.2013.07.050 |
| [19] | Shlyk, V. A., Master corner polyhedron: Vertices, Eur. J. Oper. Res, 226, 203-210 (2013) · Zbl 1292.90209 · doi:10.1016/j.ejor.2012.11.011 |
| [20] | Shlyk, V. A., Polyhedral approach to integer partitions, J. Combinat. Math. Combinat. Comput, 89, 113-128 (2014) · Zbl 1307.05018 |
| [21] | Vroublevski, A. S.; Shlyk, V. A., Computing vertices of integer partition polytopes, Informatics, 4, 34-48 (2015) |
| [22] | Weisstein, E. W., Partition |
| [23] | Yang, D. (2018). University of California, Los Angeles. Personal communication. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
