Monotonicity of normalized minimum permanents

← Minc’s list

Minc’s list · Conjecture 6

Monotonicity of normalized minimum permanents

Open

Posed by
Minc
First posed
1965

Statement

Posed by H. Minc in the 1965 survey of Marcus and Minc; it is Conjecture 6 in Minc’s catalogue.

Conjecture 6. Let \(\Lambda_v^k\) be the set of \(v\times v\) \((0,1)\)-matrices with every row and column sum equal to \(k\). For a fixed \(v\),

\[ \widetilde m(v,k)=\min\Bigl\{\operatorname{per}\Bigl(\tfrac1k A\Bigr) : A\in\Lambda_v^k\Bigr\} \]

is monotone decreasing in \(k\).

Here \(A/k\) is doubly stochastic, \(\widetilde m(v,1)=1\) and \(\widetilde m(v,v)=v!/v^v\). The sources do not say whether the decrease is meant weakly or strictly; every comparison proved so far is strict.

Prior progress

  • Wanless (2007) proved \(\widetilde m(v,k+1)<\widetilde m(v,k)\) for \(k=o(v^{1/4})\), using Schrijver’s lower bound for regular bipartite graphs, and for \(k=v-o(v^{6/7})\), using the Godsil–McKay expansion for dense matrices.
  • Wanless (2007) also computed the minimum permanents for all \(v\le 11\) by exhaustive enumeration, which confirms the conjecture in those orders.
  • The exact minima at the dense end are known: \(\min_{\Lambda_v^{v-1}}\operatorname{per}\) is the derangement number, since every such matrix is equivalent to \(J-I\), and \(\min_{\Lambda_v^{v-2}}\operatorname{per}\) is the ménage number or one less than it (Henderson 1975; McKay and Wanless 1998).

Our progress so far

  • The step \(k=2\to3\) in every order. For every \(v\ge3\), \(\widetilde m(v,3)<\widetilde m(v,2)\). Wanless’s theorem gave this only for large \(v\).
  • The step \(k=v-2\to v-1\) in every order. For every \(v\ge3\), \(\widetilde m(v,v-1)<\widetilde m(v,v-2)\).
  • The step \(k=v-3\to v-2\). We proved it for every \(v\ge 6000\) and for \(v=12\) and \(13\), and found the new values \(\min_{\Lambda_{12}^9}\operatorname{per}=17{,}846{,}856\) and \(\min_{\Lambda_{13}^{10}}\operatorname{per}=238{,}012{,}092\). On this line only \(14\le v\le5999\) remains.
  • A wider sparse range. If \(v/(k(k+1))-\log v\to\infty\), for example if \(k=o\bigl(\sqrt{v/\log v}\bigr)\), then \(\widetilde m(v,k+1)/\widetilde m(v,k)\to0\). This widens Wanless’s range \(k=o(v^{1/4})\).
  • A new exact minimum. \(\min_{\Lambda_{12}^3}\operatorname{per}=113\), attained by exactly two classes. At order \(12\) the only comparisons still open are \(k=3\to4,\dots,8\to9\).

References

  1. M. Marcus and H. Minc, Permanents, Amer. Math. Monthly 72 (1965), 577–591. doi:10.1080/00029890.1965.11970575
  2. I. M. Wanless, On Minc’s sixth conjecture, Linear and Multilinear Algebra 55 (2007), 57–63. doi:10.1080/03081080600562670
  3. A. Schrijver, Counting 1-factors in regular bipartite graphs, J. Combin. Theory Ser. B 72 (1998), 122–135. doi:10.1006/jctb.1997.1798
  4. C. D. Godsil and B. D. McKay, Asymptotic enumeration of Latin rectangles, J. Combin. Theory Ser. B 48 (1990), 19–44. doi:10.1016/0095-8956(90)90128-M
  5. J. R. Henderson, Permanents of (0,1)-matrices having at most two zeros per line, Canad. Math. Bull. 18 (1975), 353–358. doi:10.4153/CMB-1975-064-6
  6. B. D. McKay and I. M. Wanless, Maximising the permanent of (0,1)-matrices and the number of extensions of Latin rectangles, Electron. J. Combin. 5 (1998), R11. doi:10.37236/1349