Circulant maxima when k ∤ n

← Minc’s list

Minc’s list · Problem 12

Circulant maxima when k ∤ n

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 12. Let \(\Lambda_n^k\) be the set of \(n\times n\) \((0,1)\)-matrices with every row and column sum equal to \(k\). If \(k\) does not divide \(n\), find an upper bound \(L<(k!)^{n/k}\) for the permanents of the circulants in \(\Lambda_n^k\). Does there exist a matrix in \(\Lambda_n^k\) whose permanent is strictly greater than that of any circulant in \(\Lambda_n^k\)?

Brègman’s theorem gives \(\operatorname{per}A\le(k!)^{n/k}\) on \(\Lambda_n^k\), with equality only for direct sums of \(k\times k\) all-ones blocks, which requires \(k\mid n\). So the first part asks for an explicit bound below Brègman’s for circulants, and the second asks whether the maximum permanent over \(\Lambda_n^k\) can be attained by a circulant.

Prior progress

  • A circulant attains the maximum when \(k\mid n\), and when \(n=m(n-k)\) with \(m\ge5\) (McKay and Wanless 1998). Wanless (1999) showed that, for fixed \(k\) or fixed \(n-k\) and \(n\) large, these are the only such cases, so the answer to the second part is generally “yes”, but with thresholds that are not explicit.
  • The answer is known for every \(n\le11\) from exhaustive computations of the maximum permanent (McKay and Wanless 1998), and complete answers follow for \(k=3\) (from Merriell’s 1980 maxima) and for \(k=n-2\).
  • No explicit general bound \(L\) for circulants had been published.

Our progress so far

  • An explicit bound for circulants. For every \(k\ge3\) and every \(n\) not divisible by \(k\), every \(k\)-regular circulant \(C\) of order \(n\) satisfies \[ \operatorname{per}C\ \le\ (k!)^{n/k}\Bigl(1-\frac{\varepsilon_k}{k^2}\Bigr)^{\lceil n/(3k^2-5k+3)\rceil}, \] with an explicit constant \(\varepsilon_k>0\); for example \(\varepsilon_3\approx0.203\). For \(k=2\) and odd \(n\), the exact maximum over circulants is \(2^{n/p}\), where \(p\) is the smallest prime factor of \(n\).
  • Effective thresholds for the second part. For every \(n>2766\) not divisible by \(4\) some matrix in \(\Lambda_n^4\) beats every circulant, and likewise for every \(n>13{,}132\) not divisible by \(5\) in \(\Lambda_n^5\). We proved explicit thresholds for all \(3\le k\le12\).
  • The line \(k=n-3\). For \(n\ge69\) a circulant attains the maximum over \(\Lambda_n^{n-3}\) if and only if \(3\mid n\); with the finite cases below, only \(17\le n\le68\) remains open on this line.
  • Exact circulant maxima up to order \(16\). We computed the maximum permanent over circulants for all pairs with \(n\le16\). This decides the second part for the whole row \(n=13\) and for many cells with \(n=14,15,16\); ten cells with \(n\le16\) remain undecided.

References

  1. H. Minc, Theory of permanents 1978–1981, Linear and Multilinear Algebra 12 (1983), 227–263. doi:10.1080/03081088308817488
  2. L. M. Brègman, Some properties of nonnegative matrices and their permanents, Soviet Math. Dokl. 14 (1973), 945–949.
  3. D. Merriell, The maximum permanent in Λₙᵏ, Linear and Multilinear Algebra 9 (1980), 81–91. doi:10.1080/03081088008817354
  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