שלחו לחבר

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

Seminar
Speaker
Alexander Guterman (Moscow State University, visiting the Weizmann Institute of Science)
Date
18/05/2022 - 11:30 - 10:30Add to Calendar 2022-05-18 10:30:00 2022-05-18 11:30:00 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 Third floor seminar room, Mathematics building, and on Zoom. See link below. אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Third floor seminar room, Mathematics building, and on Zoom. See link below.
Abstract

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

תאריך עדכון אחרון : 10/05/2022