Permanents of doubly stochastic matrices

Abstract

If A is an nxn matrix, then the permanent of A is the sum of all products of entries on each of n! diagonals of A. Also, A is called doubly stochastic if it has non-negative entries and the row and column sums are all equal to one.

A conjecture on the minimum of the permanent on the set of doubly stochastic matrices was stated by van der Waerden in 1926 and became one of the most studied conjectures for permanents. It was open for more than 50 years until, in 1981, Egorychev and Falikman independently settled it. Another conjecture (which, if it were true, would imply the van der Waerden conjecture) was originally stated by Holens in 1964 in his M.Sc. thesis at the University of Manitoba. Three years later, Dokovic independently introduced an equivalent conjecture. This conjecture is now known as the Holens-Dokovic conjecture, and while known not to be true in general, it still remains unresolved for some specific cases.

This thesis is devoted to the study of these and other conjectures on permanents.