# Is Ryser's conjecture on permanent minimizers still open?

Let $A(k,n)$ be the set of $\{0,1\}$ matrices of order $n$ with all their line sums equal to $k$.

Conjecture number 5 on the list from Minc's book, attributed to Ryser, says that if $A(k,n)$ contains incidence matrices of symmetric $(n,k,\lambda)$-designs, then the minimum permanent on $A(k,n)$ is attained at one of theses incidence matrices.

It's also number 8 on Zhan's recent list of open problems in matrix theory. As one can see there, it has been verified by Wanless up to $n=12$ but not beyond.

I wonder if, given the recent progress on permanents, there is more known now about this conjecture?

-
Does line mean one or more of row, column, and diagonal? Also, what recent progress do you mean? Gerhard "Ask Me About System Design" Paseman, 2013.04.25 – Gerhard Paseman Apr 25 '13 at 20:50
@Gerhard I think it means each row and column is of uniform weight $k$. At least the conjecture on Zhan's list considers 0-1 matrices in which every row and column has exactly $k$ 1's. – Yuichiro Fujiwara Apr 25 '13 at 21:08
@Gerhard: Yuichiro is correct. Only row and column sums need to be $k$. – Brendan McKay Apr 25 '13 at 22:19
@Gerhard: By progress I mean the new results in hyperbolic polynomials that generalize van der Waerden's conjecture and a great deal of other results. – Felix Goldberg Apr 28 '13 at 17:58

## 2 Answers

My, i.e. hyperbolic polynomials, approach falls a bit short of proving the conjecture: first of all, the bound from my inequality is $$k^n G(k)^{n-k} \frac{k!}{k^k},$$ where $G(k) = (\frac{k-1}{k})^{k-1}$; this bound is integer only if $k=1, 2, n$. So it can't be the minimum of permanents of integer matrices.

Nobody knows the exact value of the minimum for given (k,n), I have not even seen a conjecture on that. This is why sparse problem is so much more interesting than, say, the van der Waerden Conjecture. More seriously, my approach actually needs the degrees of variables $x_i$ in the polynomials $(\partial_n....\partial_{i+1}) \prod_{1 \leq i \leq n}\sum_{1 \leq j \leq n} A(i,j) x_j$. There is a simple upper bound on those degree in terms of the sparsity, but it is not sharp.

Actually $k^n (G(k)^{n-k} \frac{k!}{k^k}$ is attainable in this general setting, see my last paper in ECCC.

Now, back to Ryzer conjecture: Let A be $n \times n$ minimizer. And $a(n)$ be the number of its boolean rows (the same with columns). It follows from my approach + plus the known upper bound due to Schrijver that $$\lim_{n \rightarrow \infty} \frac{\min_{over minimizers}(a(n))}{n} = 1.$$

BTW, the same applies to mixed discriminants. Important new improvement(amazingly suggested by the Belief Propagation/ Bethe Approximation): $per(P) \geq \prod_{i,j} (1-p(i,j))^{1-p(i,j)}$, wher $P$ is doubly-stochastic http://arxiv.org/abs/1106.2844. Let $A$ be integer matrix with row and column sums equal k, $n(l)$ be the number of entries of $A$ equal $l$. Applying this new (entropic) lower bound gives the following lower bound: $Per(A) \geq k^n \prod_{1 \leq l \leq k} (\frac{k-l}{k})^{\frac{(k-l) n(l)}{k}}$.

-
Dear Leonid, we (j.c. and i) made edits to this post; hope, you are ok with them. – Suvrit Oct 19 '13 at 21:31
Here $Prod_A$ is the product polynomial $\prod_{1 \leq i \leq n}\sum_{1 \leq j \leq n} A(i,j) x_j$; $G(k) = (\frac{k-1}{k})^{k-1}, ECCC paper: eccc.hpi-web.de/report/2013/141; and the original paper: arxiv.org/abs/0711.3496 . Thanks for the editing! – leonid gurvits Oct 19 '13 at 21:47 You're welcome! Also, if you click on the 'edit' link towards the bottom left of your original answer, you can see the markup corresponding to the edited answer. – Suvrit Oct 19 '13 at 22:52 The rate of convergence:$1 - \frac{a_n}{n} \leq O(n^{-1} \log(n))$with some universal easily computable constant. – leonid gurvits Oct 20 '13 at 1:08 I forgot to mention new, very cool and accurate lower bound: let$RI(k,n$be the set of integer$n \times n$matrices with row/column sums equal$kn(l)$be the number of entries in$A \in RI(k,n)$equal$l$,$1 \leq l \leq k$. Then$Per(A) \geq – leonid gurvits Oct 24 '13 at 19:31

I'm not aware of any more progress, but if anyone knows differently, I'd love to hear!

-