Matrices below every circulant

← Minc’s list

Minc’s list · Problem 11

Matrices below every circulant

Open

Posed by
Minc
First posed
1983

Statement

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

Problem 11. Let \(\Lambda_n^k\) be the set of \(n\times n\) \((0,1)\)-matrices with every row and column sum equal to \(k\). Does there exist a matrix in \(\Lambda_n^k\) whose permanent is strictly smaller than that of any circulant in \(\Lambda_n^k\)?

In other words: for which pairs \((n,k)\) is the minimum permanent over \(\Lambda_n^k\) not attained by a circulant? Call a matrix that does better than every circulant a beater.

Prior progress

  • The minimum permanent over \(\Lambda_n^k\) is known for all \(n\le11\) by exhaustive enumeration (Wanless). A beater exists exactly for the \(15\) pairs \((5,3)\), \((9,3)\), \((10,3)\), \((11,3)\), \((8,4)\), \((9,4)\), \((10,4)\), \((11,4)\), \((7,5)\), \((9,6)\), \((10,6)\), \((9,7)\), \((10,7)\), \((11,8)\) and \((11,9)\).
  • There is never a beater for \(k\in\{1,2,n-1,n\}\). For \(k=n-2\) the minimizers were characterized by Henderson (1975) and McKay and Wanless (1998), from which it follows that a beater exists exactly when \(n\ge5\) is odd.
  • Schrijver (1998) and Wanless (2006) showed that the minimum permanent grows like \(\beta_k^{\,n}\) with \(\beta_k=(k-1)^{k-1}/k^{k-2}\).

Our progress so far

  • Sparse matrices. For every fixed \(k\ge3\) a beater exists for all large \(n\), and more generally whenever \(k^3\log n=o(n)\). For fixed \(k\) the existence also follows by combining Csikvári’s 2016 theorem on vertex-transitive graphs with Wanless’s result above.
  • Dense matrices, explicitly. A beater exists for \(k=n-3\) whenever \(n\ge93{,}570\), and for \(k=n-4\) whenever \(n\ge163{,}521\).
  • The line \(k=n-3\) up to \(n=18\). There is no beater for \(n\le8\) and there is one for \(9\le n\le18\); the cases \(12\le n\le18\) are new. We also found the exact minima \(17{,}846{,}856\) over \(\Lambda_{12}^9\) and \(238{,}012{,}092\) over \(\Lambda_{13}^{10}\), both below every circulant, and beaters for \(k=n-4\) at \(n=16,17,18\).
  • Cubic matrices beyond order \(11\). For \((12,3)\) there is no beater, because the minimum \(113\) is attained by a circulant. For \((13,3)\) there is: the minimum is \(153\), while every circulant has permanent at least \(159\). For \((14,3)\) we found a matrix with permanent \(213\), below every circulant (\(229\)).

References

  1. H. Minc, Theory of permanents 1978–1981, Linear and Multilinear Algebra 12 (1983), 227–263. doi:10.1080/03081088308817488
  2. 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
  3. 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
  4. A. Schrijver, Counting 1-factors in regular bipartite graphs, J. Combin. Theory Ser. B 72 (1998), 122–135. doi:10.1006/jctb.1997.1798
  5. I. M. Wanless, Addendum to Schrijver’s work on minimum permanents, Combinatorica 26 (2006), 743–745. doi:10.1007/s00493-006-0040-z
  6. I. M. Wanless, On Minc’s sixth conjecture, Linear and Multilinear Algebra 55 (2007), 57–63. doi:10.1080/03081080600562670
  7. P. Csikvári, Matchings in vertex-transitive bipartite graphs, Israel J. Math. 215 (2016), 99–134. doi:10.1007/s11856-016-1375-9