COMPUTING VERTICES OF INTEGER PARTITION POLYTOPES
Abstract
The paper describes a method of generating vertices of the polytopes of integer partitions that was used by the authors to calculate all vertices and support vertices of the partition polytopes for all n ≤ 105 and all knapsack partitions of n ≤ 165. The method avoids generating all partitions of n. The vertices are determined with the help of sufficient and necessary conditions; in the hard cases, the well-known program Polymake is used. Some computational aspects are exposed in more detail. These are the algorithm for checking the criterion that characterizes partitions that are convex combinations of two other partitions; the way of using two combinatorial operations that transform the known vertices to the new ones; and employing the Polymake to recognize a limited number (for small n) of partitions that need three or more other partitions for being convexly expressed. We discuss the computational results on the numbers of vertices and support vertices of the partition polytopes and some appealing problems these results give rise to.
About the Authors
A. S. Vroublevski
ИООО «Управляющая компания ”Атлант-М”»
Belarus
Belarus
V. A. Shlyk
Командно-инженерный институт МЧС Республики Беларусь
Belarus
Belarus
References
1. Эндрюс, Г. Теория разбиений / Г. Эндрюс. – М. : Наука, 1982. – 256 с.
2. Эйлер, Л. Введение в анализ бесконечных / Л. Эйлер. – М. : Гос. изд. физ.-мат. лит., 1961. – Т. 1. – 316 с.
3. Dickson, L.E. History of the Theory of Numbers / L.E. Dickson. – Vol. II : Diophantine Analysis. – Washington : Carnegie Inst., 1919. – 520 p.
4. Шлык, В.А. Политопы разбиений чисел / В.А. Шлык // Весці Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 1996. – № 3. – С. 89–92.
5. Shlyk, V.A. Polytopes of partitions of numbers / V.A. Shlyk // European J. Combin. – 2005. – Vol. 26, № 8. – P. 1139–1153.
6. Емеличев, В.А. Многогранники, графы, оптимизация (комбинаторная теория многогранников) / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. – М. : Наука, 1981. – 341 с.
7. Шлык, В.А. Комбинаторные операции порождения вершин политопа разбиений чисел / В.А. Шлык // Докл. Нац. акад. наук Беларуси. – 2009. – Т. 53, № 6. – С. 27–32.
8. Холл, М. Комбинаторика / М. Холл. – М. : Мир, 1970. – 424 с.
9. Gupta, H. Tables of partitions / H. Gupta, C.E. Gwyther, C.P. Winter // Royal society mathematical tables. – Vol. 4. – Cambridge : University Press, 1958. – 132 p.
10. Sloane, N.J.A. a(n) = number of partitions of n (the partition numbers) [Electronic resource] / N.J.A. Sloane. – 2010. – Mode of access : http://oeis.org/A000041. – Date of access : 11.10.2015.
11. Zoghbi, A. Fast algorithms for generating integer partitions / A. Zoghbi, I. Stojmenovic // Intern. J. Computer Math. – 1998. – Vol. 70. – P. 319–332.
12. Рейнгольд, Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. – М. : Мир, 1980. – 476 с.
13. Nijenhius, A. A method and two algorithms on the theory of partitions / A. Nijenhius, H.S. Wilf // J. Comb. Theory A. – 1975. – Vol. 18. – P. 219–222.
14. Riha, W. Efficient algorithms for doubly and multiply restricted partitions / W. Riha, K.R. James // Algorithm 29. Computing. – 1976. – Vol. 16. – P. 163–168.
15. Constant time generation of integer partitions / K. Yamanaka [et al.] // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. – 2007. – Vol. E90-A, № 5. – P. 888–895.
16. Knuth, D.E. Generating all partitions. Pre-fascicle 3B of The Art of Computer Programming. A draft of sections 7.2.1.4-5 [Electronic resource] / D.E. Knuth. – 2004. – Mode of access : http://www.cs.utsa.edu/~wagner/knuth/fasc3b.pdf. – Date of access : 11.10.2015.
17. Kelleher, J. Generating all partitions: a comparison of two encodings [Electronic resource] / J. Kelleher, В. O'Sullivan. – 2009. – Mode of access : http://arxiv.org/pdf/0909.2331v1.pdf. – Date of access : 11.10.2015.
18. Opdyke, J.D. A unified approach to algorithms generating unrestricted and restricted integer compositions and integer partitions / J.D. Opdyke // J. Math. Model. Algor. – 2010. – Vol. 9, № 1. – P. 53–97.
19. Stojmenovic, I. Generating all and random instances of a combinatorial object / I. Stojmenovic // Handbook of applied algorithms: solving scientific, engineering, and practical problem. – Hoboken : John Wiley&Sons, 2008. – P. 1–38.
20. Shlyk, V.A. Number of vertices of the integer partition polytope [Electronic resource] / V.A. Shlyk. – 2012. – Mode of access : http://oeis.org/A203898. – Date of access : 11.10.2015.
21. Shlyk, V.A. Number of support partitions-vertices [Electronic resource] / V.A. Shlyk. – 2012. – Mode of access : http://oeis.org/A203899. – Date of access : 11.10.2015.
22. Ehrenborg, R. Number of knapsack partitions of n [Electronic resource] / R. Ehrenborg. – 2005. – Mode of access : http://oeis.org/A108917. – Date of access : 11.10.2015.
23. Шлык, В.А. Критерий представления разбиений чисел в виде выпуклой комбинации двух разбиений / В.А. Шлык // Вестник БГУ. Сер. 1. – 2009. – № 2. – С. 109–114.
24. Shlyk, V.A. Integer partitions from the polyhedral point of view / V.A. Shlyk // Electron. Notes Discrete Math. – 2013. – Vol. 43. – P. 319–327.
25. Shlyk, V.A. Polyhedral approach to integer partitions / V.A. Shlyk // Journal of Combinatorial Mathematics and Combinatorial Computing. – 2014. – Vol. 89. – P. 113–128.
26. Gawrilow, E. Polymake: a framework for analyzing convex polytopes / E. Gawrilow, E.M. Joswig // Polytopes – combinatorics and computation. – Basel : Birkhäuser, 2000. – P. 43–73.
27. Шлык, В.А. О вершинах политопов разбиений чисел / В.А. Шлык // Докл. Нац. акад. наук Беларуси. – 2008. – Т. 52, № 3. – С. 5–10.
28. Handbook of Mathematical Functions / M. Abramowitz, I.A. Stegun [eds]. – Applied Math. Series 55. – Washington : Government Printing Office, 1972. – 1046 p.
29. Barvinok, A.I. Polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed / A.I. Barvinok // Math. Oper. Res. – 1994. – Vol. 19. – P. 769–779.
30. Effective lattice point counting in rational convex polytopes / J.A. De Loera [et al.] // Journal of Symbolic Computation. – 2004. – Vol. 38, № 4. – P. 1273–1302.
31. Ehrenborg, R. The Möbius function of partitions with restricted block sizes / R. Ehrenborg, M.A. Readdy // Adv. in Appl. Math. – 2007. – Vol. 39, № 3. – P. 283–292.
Review
For citations:
Vroublevski A.S., Shlyk V.A. COMPUTING VERTICES OF INTEGER PARTITION POLYTOPES. Informatics. 2015;(4):34-48. (In Russ.)
Views: 900
Email this article 