Том 23, номер 4, 2016 г., Стр. 35-101

УДК 519.1
Тараненко А. А.
Перманенты многомерных матриц: свойства и приложения

Аннотация:
Перманентом многомерной матрицы называется сумма по всем диагоналям произведений элементов, стоящих на диагоналях. В этом обзоре рассмотрены основные свойства многомерного перманента, достаточные условия его положительности, известные верхние оценки и особенности перманентов полистохастических матриц. Установлено, что число различных комбинаторных объектов может быть выражено с помощью многомерного перманента. Отдельное внимание уделено числу 1-факторов в униформных гиперграфах и числу трансверсалей в латинских гиперкубах.
Табл. 1, библиогр. 63.

Ключевые слова: перманент, многомерная матрица, стохастическая матрица, полистохастическая матрица, трансверсаль латинского гиперкуба, 1-фактор в униформном гиперграфе.

DOI: 10.17377/daio.2016.23.517

Тараненко Анна Александровна ¹
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: taattg@mail.ru

Статья поступила 13 ноября 2015 г.

Литература

[1] Августинович С. В. Многомерные перманенты в задачах перечисления // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 5. С. 3–5.

[2] Брэгман Л. М. Некоторые свойства неотрицательных матриц и их перманентов // Докл. АН СССР. 1973. Т. 211, № 1. С. 27–30.

[3] Егорычев Г. П. Решение проблемы Ван дер Вардена для перманентов // Сиб. мат. журн. 1981. Т. 22, № 6. С. 65–71.

[4] Минк Х. Перманенты. М.: Мир, 1982. 213 c.

[5] Онлайн-энциклопедия целочисленных последовательностей // https://oeis.org.

[6] Соколов Н. П. Пространственные матрицы и их приложения. М.: Физматлит, 1960. 299 с.

[7] Соколов Н. П. Введение в теорию многомерных матриц. Киев: Наукова думка, 1972. 177 с.

[8] Фаликман Д. И. Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы // Мат. заметки. 1981. Т. 29, № 6. С. 931–938.

[9 Aharoni R., Georgakopoulos A., Sprüssel P. Perfect matchings in $r$-partite $r$-graphs // Eur. J. Comb. 2009. Vol. 30. P. 39–42.

[10] Alon N., Friedland S. The maximum number of perfect matchings in graphs with a given degree sequence // Electron. J. Comb. 2008. Vol. 15, No. N13. P. 1–2.

[11] Balasubramanian L. On transversals in Latin squares // Linear Algebra Appl. 1990. Vol. 131. P. 125–129.

[12] Bapat R. B. A stronger form of the Egorychev–Falikman theorem on permanents // Linear Algebra Appl. 1984. Vol. 63. P. 95–100.

[13] Baranyai Zs. On the factorization of the complete uniform hypergraph // Infinite and Finite Sets (Hajnal A., Rado T., Sós V.T., eds.). Vol. 1. Amsterdam: North-Holland, 1973. P. 91–108. (Colloq. Math. Soc. J. Bolyai; Vol. 10.)

[14] Barvinok A., Samorodnitsky A. Computing the partition function for perfect matchings in a hypergraph // Comb. Probab. Comput. 2011. Vol. 20, No. 6. P. 815–835.

[15] Brualdi R. A., Csima J. Extremal plane stochastic matrices of dimension three // Linear Algebra Appl. 1975. Vol. 11. P. 105–133.

[16] Cauchy A.-L. Mèmoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions operées entre les variables qu’elles renferment // J. Éc. Polytech., Math. 1815. Vol. 10, No. 17. P. 29–112.

[17] Cayley A. On the theory of determinants // Trans. Camb. Philos. Soc. 1849. Vol. 8. P. 75–88.

[18] Cheon G.-S., Wanless I. M. An update on Minc’s survey of open problems involving permanents // Linear Algebra Appl. 2005. Vol. 403. P. 314–342.

[19] Cifuentes D., Parrilo P. A. An efficient tree decomposition method for permanents and mixed discriminants // Linear Algebra Appl. 2016. Vol. 493. P. 45–81.

[20] Csima J. Multidimensional stochastic matrices and patterns // J. Algebra. 1970. Vol. 14. P. 194–202.

[21] Cutler J., Radcliffe A. J. An entropy proof of the Kahn–Lovàsz theorem // Electron. J. Comb. 2011. Vol. 18, No. 1. P10, 1–9.

[22] Daykin D. E., Häggkvist R. Degrees giving independent edges in a hypergraph // Bull. Aust. Math. Soc. 1981. Vol. 23, No. 1. P. 103–109.

[23] Donovan D., Johnson K., Wanless I. M. Permanents and determinants of Latin squares // J. Comb. Des. 2016. Vol. 24, No. 3. P. 132–148.

[24] Dow S. J., Gibson P. M. An upper bound for the permanent of a 3-dimensional (0,1)-matrix // Proc. Amer. Math. Soc. 1987. Vol. 99, No. 1. P. 29–34.

[25.] Dow S. J., Gibson P. M. Permanents of $d$-dimensional matrices // Linear Algebra Appl. 1987. Vol. 90. P. 133–145.

[26] Eberhard S., Manners F., Mrazovic´ R. Additive triples of bijections, or the toroidal semiqueens problem // arXiv:1510.05987v3.

[27] Gibson P. M. Combinatorial matrix functions and 1-factors of graphs // SIAM J. Appl. Math. 1970. Vol. 19. P. 330–333.

[28] Glebov R., Luria Z. On the maximum number of Latin transversals // J. Comb. Theory, Ser. A. 2016. Vol. 141. P. 136–146.

[29] Gurvits L. Van der Waerden/Schrijver–Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: One theorem for all // Electron. J. Comb. 2008. Vol. 15. P. 1–26. R66.

[30] Gyires B. Elementary proof for a Van der Waerden’s conjecture and related theorems // Comput. Math. Appl. 1996. Vol. 31, No. 10. P. 7–21.

[31] Gyires B. Contribution to van der Waerden’s conjecture // Comput. Math. Appl. 2001. Vol. 42. P. 1431–1437.

[32] Hell S. On the number of Birch partitions // Discrete Comput. Geom. 2008. Vol. 40. P. 586–594.

[33] Hell S. On the number of colored Birch and Tverberg partitions // Electron. J. Comb. 2014. Vol. 21, No. 3. P3.23.

[34] Jurkat W. B., Ryser H. J. Extremal configurations and decomposition theorems // J. Algebra. 1968. Vol. 8. P. 194–222.

[35] Krotov D. S., Potapov V. N. $n$-Ary quasigroups of order 4 // SIAM J. Discrete Math. 2009. Vol. 23, No. 2. P. 561–570.

[36] Kühn D., Osthus D. Embedding large subgraphs into dense graphs // Surv. Comb. New York: Cambridge Univ. Press, 2009. P. 137–167 (London Math. Soc. Lect. Note Ser.; Vol. 365).

[37] Laurent M., Schriver A. On Leonid Gurvits’s proof for permanents // Amer. Math. Mon. 2010. Vol. 117. P. 903–911.

[38] Linial N., Luria Z. An upper bound on the number of Steiner triple systems // Random Struct. Algorithms. 2013. Vol. 34, No 4. P. 399–406.

[39] Linial N., Luria Z. An upper bound on the number of high-dimensional permutations // Combinatorica. 2014. Vol. 34, No. 4. P. 471–486.

[40] Linial N., Luria Z. On the vertices of the d-dimensional Birkhoff polytope // Discrete Comput. Geom. 2014. Vol. 51. P. 161–170.

[41] Lo A., Markström K. Perfect matchings in 3-partite 3-uniform hypergraphs // J. Comb. Theory, Ser. A. 2014. Vol. 127. P. 22–57.

[42] Marcus M., Minc H. On a conjecture of B. L. van der Waerden // Proc. Camb. Philos. Soc. 1967. Vol. 63. P. 305–309.

[43] Marcus M., Newman M. On the minimum of the permanent of a doubly stochastic matrix // Duke Math. J. 1959. Vol. 26. P. 61–72.

[44] McKay B. D., McLeod J. C., Wanless I. M. The number of transversals in a Latin square // Des. Codes Cryptogr. 2006. Vol. 40. P. 269–284.

[45] McKay B. D.,Wanless I. M. A census of small Latin hypercubes // SIAM J. Discrete Math. 2008. Vol. 22. P. 719–736.

[46] Minc H. Upper bound for permanents of (0,1)-matrices // Bull. Amer. Math. Soc. 1963. Vol. 69. P. 789–791.

[47] Muir T. A treatise on the theory of determinants. London: Macmillan and Co., 1882. 774 p.

[48] Pikhurko O. Perfect matchings and $K^{3}_{4}$-tilings in hypergraphs of large code-gree // Graphs Comb. 2008. Vol. 24, No. 4. P. 391–404.

[49] Potapov V. N. On the multidimensional permanent and $q$-ary designs // Sib. Elektron. Mat. Izv. 2014. Vol. 11. P. 451–456.

[50] Radhakrishnan J. An entropy proof of Bregman’s theorem // J. Comb. Theory, Ser. A. 1997. Vol. 77, No. 1. P. 161–164.

[51] Rödl V., Rucinski A., Szemerèdi E. Perfect matchings in large uniform hypergraphs with large minimum collective degree // J. Comb. Theory, Ser. A. 2009. Vol. 116, No. 3. P. 613–636.

[52] Ryser H. J. Neuere Probleme der Kombinatorik // Vortrage über Kombinatorik (Germany, Oberwolfach, July 24–29, 1967). Oberwolfach: Math. Forschungsinst. Oberwolfach, 1967. P. 69–91.

[53] Schrijver A. A short proof of Minc’s conjecture // J. Comb. Theory, Ser. A. 1978. Vol. 25, No. 1. P. 80–83.

[54] Schrijver A. Counting 1-factors in regular bipartite graphs // J. Comb. Theory, Ser. B. 1998. Vol. 72, No. 1. P. 122–135.

[55] Soules G. W. Permanental bounds for nonnegative matrices via decomposition // Linear Algebra Appl. 2005. Vol. 394. P. 73–89.

[56] Sun Z.-W. An additive theorem and restricted sumsets // Math. Res. Lett. 2008. Vol. 15, No. 6. P. 1263–1276.

[57] Taranenko A. A. Upper bounds on the permanent of multidimensional (0,1)-matrices // Sib. Elektron. Mat. Izv. 2014. Vol. 11. P. 958–965.

[58] Taranenko A. A. Multidimensional permanents and an upper bound on the number of transversals in Latin squares // J. Comb. Des. 2015. Vol. 23. P. 305–320.

[59] Taranenko A. A. Upper bounds on the numbers of 1-factors and 1-factorizations of hypergraphs // arXiv:1503.08270v1.

[60] Tichy M. C. Sampling of partially distinguishable bosons and the relation to the multidimensional permanent // Phys. Rev. A. 2015. Vol. 91, No. 2. 022316. P. 1–13.

[61] Vardi I. Computational recreations in mathematics. Redwood City, CA: Addison-Wesley, 1991.

[62] Wanless I. M. Transversals in Latin squares: a survey // Surv. Comb. Cambridge: Cambridge Univ. Press, 2011. P. 403–437 (London Math. Soc. Lect. Note Ser.; Vol. 392).

[63] Wanless I. M., Webb B. S. The existence of Latin squares without orthogonal mates // Des. Codes Cryptogr. 2006. Vol. 40. P. 131–135.