Maximum permanent when k ∤ n

← Minc’s list

Minc’s list · Problem 4

Maximum permanent when k ∤ n

Open

Posed by
Minc
First posed
1978

Statement

Posed by H. Minc; it is Problem 4 in his 1978 book.

Problem 4. Let \(\Lambda_n^k\) be the set of \(n\times n\) \((0,1)\)-matrices with every row and column sum equal to \(k\). Find the maximal value of \(\operatorname{per}A\) over \(\Lambda_n^k\) in case \(k\) does not divide \(n\).

When \(k\) divides \(n\), Brègman’s theorem gives the maximum \((k!)^{n/k}\), attained by a direct sum of all-ones blocks \(J_k\). Write \(M(n,k)\) for the maximum.

Prior progress

  • For \(n=tk+r\) with \(0\le r<k\), \((k!)^t\,r!\le M(n,k)\le(k!)^{n/k}\); the upper bound is Brègman’s (1973) and the lower bound is due to Wanless (2003).
  • The case \(k=2\) is elementary, and Merriell (1980) solved \(k=3\). Bol’shakov (1986) found \(M(4t+1,4)\). Merriell’s conjectured general formulas, catalogue Conjectures 25 and 26, turned out to be false.
  • Dense cases are known: line sum \(n-2\) (Brualdi, Goldwasser and Michael 1988; McKay and Wanless 1998), and \(M(mk,(m-1)k)\) for \(m\ge5\) (McKay and Wanless 1998). Exact values are tabulated for \(n\le11\) and for further cells up to \(n=18\).
  • Wanless (1999, 2003) showed that for fixed \(k\) the maximizers eventually stabilize and have small components, but with thresholds that are not explicit.

Our progress so far

  • The line \(k=n-3\) for all \(n\ge69\). For every \(n\ge69\), the maximum of \(\operatorname{per}A\) over \(\Lambda_n^{n-3}\) is attained, uniquely up to permutations, by the complement of an explicit \(3\)-regular zero pattern \(E_n\) built from blocks \(J_3\) and one small exceptional block. For example, for \(n=3t\ge69\), \[ M(3t,3t-3)=\int_0^\infty e^{-x}\,(x^3-9x^2+18x-6)^t\,dx. \] Since \(k=n-3\) never divides \(n\) when \(n\ge7\), and the values for \(n\le15\) were already known, this line of the problem is open only for \(16\le n\le68\).
  • Toward the remaining range. For \(n\ge10\), the same answer holds whenever every connected component of the zero pattern has order at most \(13\), and for connected zero patterns without a copy of \(K_{3,3}\) minus an edge it holds for all \(n\ge42\).
  • The line \(k=n-4\). For \(n\ge12\), the analogous explicit pattern is the unique maximizer among zero patterns whose components have order at most \(7\). This restricted result does not yet settle any unrestricted case.

References

  1. H. Minc, Permanents, Encyclopedia of Mathematics and its Applications 6, Addison-Wesley, 1978.
  2. D. Merriell, The maximum permanent in Λₙᵏ, Linear and Multilinear Algebra 9 (1980), 81–91. doi:10.1080/03081088008817354
  3. R. A. Brualdi, J. L. Goldwasser and T. S. Michael, Maximum permanents of matrices of zeros and ones, J. Combin. Theory Ser. A 47 (1988), 207–245.
  4. 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
  5. I. M. Wanless, Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum, Discrete Math. 205 (1999), 191–205. doi:10.1016/S0012-365X(99)00048-5
  6. I. M. Wanless, A lower bound on the maximum permanent in Λₙᵏ, Linear Algebra Appl. 373 (2003), 153–167. doi:10.1016/S0024-3795(02)00715-2