Функция перманента матриц и ее значения

Доклад основан на работах [2, 3, 4, 5].

Две важные в алгебре и комбинаторике матричные функции — это перманент и определитель. Определитель всем известен, а перманент состоит из тех же слагаемых, что и определитель, но все они берутся со знаком плюс. Однако свойства функции перманент значительно сложней. Например, методом Гаусса определитель вычисляется за полиномиальное время, тогда как вопрос существования полиномиального алгоритма вычисления перманента открыт. В этой связи актуален целый ряд вопросов о связи перманента и определителя и о том, какие значения может принимать функция перманента.

Среди вопросов, которые будут обсуждаться в докладе:

проблема Полиа конвертации перманента и определителя [7],
проблема Брюальди-Ньюмана существования границы подряд идущих значений перманента (0,1)-матриц [1],
положительное решение проблемы Ванга-Кройтера, поставленной в 1974, [6, 8], полученное в [2].

Список литературы

[1] R. A. Brualdi, M. Newman, Some theorems on permanent, J. Res. Natl. Bur. Stand., Sect. B 69B:3 (1965) 159–163.

[2] M.V. Budrevich, A.E. Guterman, Krauter conjecture on permanents is true, Journal of Combinatorial Theory – Ser. A, 162 (2019) 306-343.

[3] M. Budrevich, G. Dolinar, A. Guterman, B. Kuzma, Graph characterization of fully indecomposable nonconvertible (0,1)-matrices with minimal number of ones, Ars Mathematica Contemporanea, 17:1 (2019) 141-151

[4] G. Dolinar, A.E. Guterman, B. Kuzma, M. Orel, On the Polya permanent problem over finite fields, European J. of Combinatorics, 32 (2011) 116-132.

[5] A.E. Guterman, K.A. Taranin, On the values of the permanent of (0,1)-matrices, Linear Algebra and Its Application, 552 (2018) 256-276.

[6] A.R. Krauter, Recent results on permanents of (+1, -1)-matrices, Ber. No. 249, Berichte, 243-254, Forschungszentrum Graz, Graz, 1985.

[7] G. Polya, Aufgabe, 424, Arch. Math. Phys. 20:3 (1913) 271.

[8] E.T.H. Wang, On permanents of (+1, -1)-matrices, Israel J. Math., 18 (1974) 353-361.