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,λ)-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?

Answer

My, i.e. hyperbolic polynomials, approach falls a bit short of proving the conjecture: first of all, the bound from my inequality
is knG(k)nkk!kk,
where G(k)=(k1k)k1; 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 xi in the polynomials (n....i+1)1in1jnA(i,j)xj. There is a simple upper bound
on those degree in terms of the sparsity, but it is not sharp.

Actually kn(G(k)nkk!kk is attainable in this general setting, see my last paper in ECCC.

Now, back to Ryzer conjecture: Let A be n×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

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}}.

Attribution
Source : Link , Question Author : Felix Goldberg , Answer Author : Brendan McKay

Leave a Comment