Permanent values of 3-regular matrices

← Minc’s list

Minc’s list · Problem 3

Permanent values of 3-regular matrices

Open

Posed by
Greenstein
First posed
1978

Statement

Posed by B. Greenstein; it is Problem 3 in Minc’s 1978 book.

Problem 3. Let \(\Lambda_n^3\) be the set of \(n\times n\) \((0,1)\)-matrices with every row and column sum equal to \(3\). Find all the values that \(\operatorname{per}A\) can take for \(A\in\Lambda_n^3\).

Equivalently, determine the possible numbers of perfect matchings of \(3\)-regular bipartite graphs with \(n\) vertices on each side. Write \(\Pi_3(n)\) for this set of values.

Prior progress

  • The extremes are well understood. Merriell (1980) found the maximum in every order, and Voorhoeve (1979) proved \(\operatorname{per}A\ge6(4/3)^{n-3}\), whose base is optimal by Schrijver (1998).
  • Bol’shakov (1986) determined \(\Pi_3(n)\) for \(n\le8\), and McKay and Wanless (1998) and Wanless (2007) computed the maximum and minimum for \(n\le11\).
  • Shevelev (2013) described the values for symmetric matrices; several authors studied circulants, which take few values. Computing the permanent on \(\Lambda_n^3\) is #P-complete (Dagum and Luby 1992), which makes a simple general answer unlikely.
  • R. P. P. McKone posted the complete value sets for \(n=9,10,11\) to the OEIS in July 2025.

Our progress so far

  • Exponentially many values. For every \(n\ge19\), \(\lvert\Pi_3(n)\rvert\ge\lceil 8^{(n-19)/14}\rceil\), so \(\lvert\Pi_3(n)\rvert\) grows at least like \(1.16^n\).
  • Independent confirmation for \(n=9\) and \(10\). We confirmed that \(\lvert\Pi_3(9)\rvert=32\) and \(\lvert\Pi_3(10)\rvert=61\), in agreement with McKone’s lists. For example, every integer from \(60\) to \(90\) is a permanent of some matrix in \(\Lambda_{10}^3\).
  • Larger orders. We also showed \(\lvert\Pi_3(17)\rvert\ge530\), \(\lvert\Pi_3(21)\rvert\ge2104\) and \(\lvert\Pi_3(28)\rvert\ge13{,}429\).

References

  1. H. Minc, Permanents, Encyclopedia of Mathematics and its Applications 6, Addison-Wesley, 1978.
  2. M. Voorhoeve, A lower bound for the permanents of certain (0,1)-matrices, Indag. Math. (Proc.) 82 (1979), 83–86. doi:10.1016/1385-7258(79)90012-X
  3. D. Merriell, The maximum permanent in Λₙᵏ, Linear and Multilinear Algebra 9 (1980), 81–91. doi:10.1080/03081088008817354
  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. V. Shevelev, Spectrum of permanent’s values and its extremal magnitudes in Λₙ³ and Λₙ(α, β, γ), J. Optim. (2013), 289829. doi:10.1155/2013/289829
  6. OEIS, sequences A185178 and A185179, with R. P. P. McKone’s complete and known values.