Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
    
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 $k$ $n(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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.