The resolution of Kräuter's conjecture on the permanent, and beyond

The talk is based on joint works with Mikhail Budrevich and Constantine Taranin.

Two important functions in matrix theory, the determinant and the permanent, have similar definitions.  However, while the determinant may be computed in polynomial time, it is an open question whether fast algorithms computing the permanent exist.  Therefore, any bounds on the permanent are of interest.

The class of matrices with entries 1 and -1 is very important in algebra, combinatorics, and their various applications.  In 1974, Wang posed the problem of finding an upper bound for the permanent of a (1, -1)-matrix.  This problem has appeared in several monographs and survey papers.  Kräuter later made a conjecture about the form of this bound.

In this talk we present a complete solution of Wang’s problem, obtained by proving Kräuter’s conjecture.  In particular, we characterize the matrices with the maximal possible permanent among the matrices of a given rank.

Also, we will discuss the permanents of (0,1)-matrices.  In 1965, Brualdi and Newman showed that every integer in the interval [0,2^{n-1}] is the permanent of some n x n (0,1)-matrix.  We improve their bound by showing that this is true for every integer in an interval somewhat larger than [0,2^n].

================================================

https://us02web.zoom.us/j/87856132062

Meeting ID: 878 5613 2062