Integrality of the minimum permanent

← Minc’s list

Minc’s list · Conjecture 24

Integrality of the minimum permanent

Open

Posed by
Minc
First posed
1983

Statement

Posed by H. Minc in 1983, among the new conjectures of his survey of the theory of permanents for 1978–1981.

Conjecture 24. Let \(\Lambda_n^k\) be the set of \(n\times n\) \((0,1)\)-matrices with every row and column sum equal to \(k\), and let \(\overline\Lambda_n^k\) be the set of \(n\times n\) matrices with nonnegative integer entries and every row and column sum equal to \(k\). Then the permanent attains its minimum over \(\overline\Lambda_n^k\) at a \((0,1)\)-matrix:

\[ \min\bigl\{\operatorname{per}A : A\in\overline\Lambda_n^k\bigr\}=\min\bigl\{\operatorname{per}A : A\in\Lambda_n^k\bigr\}. \]

The entries must be integers, as in Minc’s original statement; Cheon and Wanless’s notation omits the word. Over real entries the statement fails for every \(k<n\), since \(\tfrac kn\) times the all-ones matrix has smaller permanent by van der Waerden’s theorem.

Prior progress

  • Schrijver (1998) proved \(\operatorname{per}A\ge\bigl((k-1)^{k-1}/k^{k-2}\bigr)^n\) on the integer class, with an asymptotically optimal base, and Wanless (2006) showed that the binary and integer minima have the same exponential rate. Neither decides the conjecture in any fixed order.
  • The cases \(k=1\), \(k=2\) and \(k=n\) are elementary; for \(k=n\) the minimum \(n!\) is attained only at the all-ones matrix, by van der Waerden’s theorem.
  • Cheon and Wanless (2005) reported no progress.

Our progress so far

  • All orders up to seven, and \((n,k)=(8,3)\). For every \(1\le k\le n\le 7\) and for \((n,k)=(8,3)\), the two minima agree and every minimizer over \(\overline\Lambda_n^k\) is a \((0,1)\)-matrix. At \((8,3)\), for example, the minimum is \(33\).
  • No local counterexample for \(k=n-1\). Any fixed non-binary defect, padded to order \(n\), gives matrices in \(\overline\Lambda_n^{n-1}\) whose permanent exceeds the binary minimum (the derangement number) for all large \(n\). A counterexample family on this line would need defects that grow with \(n\).
  • The minimizers for \(k=2\). Every minimizer in \(\overline\Lambda_n^2\) is a \((0,1)\)-matrix whose bipartite graph is a single cycle, so it has permanent \(2\).

References

  1. H. Minc, Theory of permanents 1978–1981, Linear and Multilinear Algebra 12 (1983), 227–263. doi:10.1080/03081088308817488
  2. A. Schrijver, Counting 1-factors in regular bipartite graphs, J. Combin. Theory Ser. B 72 (1998), 122–135. doi:10.1006/jctb.1997.1798
  3. I. M. Wanless, Addendum to Schrijver’s work on minimum permanents, Combinatorica 26 (2006), 743–745. doi:10.1007/s00493-006-0040-z
  4. I. M. Wanless, On Minc’s sixth conjecture, Linear and Multilinear Algebra 55 (2007), 57–63. doi:10.1080/03081080600562670