4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Commented Apr 25, 2013 at 20:50
  • $\begingroup$ @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. $\endgroup$ Commented Apr 25, 2013 at 21:08
  • $\begingroup$ @Gerhard: Yuichiro is correct. Only row and column sums need to be $k$. $\endgroup$ Commented Apr 25, 2013 at 22:19
  • $\begingroup$ @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. $\endgroup$ Commented Apr 28, 2013 at 17:58

2 Answers 2

6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Dear Leonid, we (j.c. and i) made edits to this post; hope, you are ok with them. $\endgroup$
    – Suvrit
    Commented Oct 19, 2013 at 21:31
  • $\begingroup$ 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! $\endgroup$ Commented Oct 19, 2013 at 21:47
  • $\begingroup$ 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. $\endgroup$
    – Suvrit
    Commented Oct 19, 2013 at 22:52
  • $\begingroup$ The rate of convergence: $1 - \frac{a_n}{n} \leq O(n^{-1} \log(n))$ with some universal easily computable constant. $\endgroup$ Commented Oct 20, 2013 at 1:08
  • $\begingroup$ 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 $\endgroup$ Commented Oct 24, 2013 at 19:31
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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