Exponential bounds for 6-regular circulants

← Minc’s list

Minc’s list · Problem 10

Exponential bounds for 6-regular circulants

Solved by us Preprint, September 2026

Posed by
Minc
First posed
1978

Statement

Posed by H. Minc; it is Problem 10 in his 1978 book. His 1983 survey misprinted \(2.99\) as \(2.29\), as Cheon and Wanless point out.

Problem 10. Let \(\Lambda_n^6\) be the set of \(n\times n\) \((0,1)\)-matrices with all row and column sums equal to \(6\). Find numbers \(m\) and \(M\) such that

\[ 2.31^n<m^n\le\operatorname{per}A\le M^n<2.99^n \]

for all \(A\in\Lambda_n^6\) and sufficiently large \(n\). Alternatively, find \(m\) and \(M\) that satisfy these inequalities for all circulants in \(\Lambda_n^6\) for sufficiently large \(n\).

Most of this was settled before our work. For all of \(\Lambda_n^6\) the best lower constant is \(m=5^5/6^4\approx2.41127\) (Schrijver 1998; Wanless 2006), and no \(M<2.99\) exists, even for circulants: Brègman’s bound \((6!)^{n/6}\), with \((6!)^{1/6}\approx2.9938\), is attained by a circulant whenever \(6\) divides \(n\). Cheon and Wanless concluded that the only remaining issue was whether the lower bound can be improved for circulants.

Resolution

We answered this question and found the best possible constant.

  • A uniform improvement. For every \(n\ge6\) and every \(6\)-regular circulant \(C\) of order \(n\), \[ \operatorname{per}C\ \ge\ \Bigl(\tfrac{3125}{1296}\,e^{7/250000}\Bigr)^{n}=(2.41133\ldots)^n. \]
  • The optimal constant. The best constant is \(h_6=\exp\bigl(2\lambda_{\Gamma_6}(1)\bigr)\), where \(\lambda_{\Gamma_6}(1)\) is the perfect-matching entropy per vertex of an explicit infinite lattice graph \(\Gamma_6\) on \(\mathbb Z^5\), of which every \(6\)-regular circulant graph is a finite quotient. Every circulant satisfies \(\operatorname{per}C\ge h_6^{\,n}\), and an explicit sequence of circulants approaches \(h_6\), so no larger constant works.
  • A bracket for \(h_6\). \(2.41133\ldots\le h_6\le2.54756\ldots\), where the upper endpoint is the exact permanent of a circulant of order \(35\).

The structural theorem is analytic, based on matching entropy and on bipartite lifts of graphs; the constant \(e^{7/250000}\) comes from exact computer-assisted certificates. That some improvement exists also follows from a 2016 theorem of Csikvári on vertex-transitive bipartite graphs with short cycles, although that paper does not mention circulants or Minc’s problem.

Read our paper →

References

  1. H. Minc, Permanents, Encyclopedia of Mathematics and its Applications 6, Addison-Wesley, 1978.
  2. A. Schrijver, Counting 1-factors in regular bipartite graphs, J. Combin. Theory Ser. B 72 (1998), 122–135. doi:10.1006/jctb.1997.1798
  3. I. M. Wanless, Addendum to Schrijver’s work on minimum permanents, Combinatorica 26 (2006), 743–745. doi:10.1007/s00493-006-0040-z
  4. 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
  5. P. Csikvári, Matchings in vertex-transitive bipartite graphs, Israel J. Math. 215 (2016), 99–134. doi:10.1007/s11856-016-1375-9
  6. P. Csikvári, Lower matching conjecture, and a new proof of Schrijver’s and Gurvits’s theorems, J. Eur. Math. Soc. 19 (2017), 1811–1844. doi:10.4171/JEMS/706
  7. M. Abért, P. Csikvári and T. Hubai, Matching measure, Benjamini–Schramm convergence and the monomer–dimer free energy, preprint (2014). arXiv:1405.6740
  8. Y. Lavi, The sharp exponential constant for 6-regular circulant matrices, preprint (2026). Paper page