Ryser’s design conjecture

← Minc’s list

Minc’s list · Conjecture 5

Ryser’s design conjecture

Open

Posed by
Ryser
First posed
1960

Statement

Suggested by H. J. Ryser in his 1960 survey of \((0,1)\)-matrices, stated as a conjecture in the 1965 list of Marcus and Minc, and Conjecture 5 in Minc’s catalogue.

Conjecture 5. Let \(\Lambda_v^k\) be the set of \(v\times v\) \((0,1)\)-matrices with every row and column sum equal to \(k\). If \(\Lambda_v^k\) contains incidence matrices of \((v,k,\lambda)\)-configurations, then the permanent attains its minimum over \(\Lambda_v^k\) at one of these incidence matrices.

Following Ryser, a \(v\times v\) \((0,1)\)-matrix \(A\) is the incidence matrix of a \((v,k,\lambda)\)-configuration if \(AA^{\mathsf T}=(k-\lambda)I+\lambda J\) with \(0<\lambda<k<v\), where \(J\) is the all-ones matrix; these are exactly the incidence matrices of symmetric \((v,k,\lambda)\) designs. The conjecture asserts only that some configuration attains the minimum, not that every configuration does or that minimizers are unique.

Prior progress

  • The family \((v,v-1,v-2)\) holds trivially, because every matrix in \(\Lambda_v^{v-1}\) is permutation-equivalent to \(J-I\).
  • Wanless (2007) found the minimum permanent over \(\Lambda_n^k\) for all \(n\le 11\) by exhaustive enumeration. The conjecture holds for every eligible pair with \(v\le12\): the Fano plane is a minimizer in \(\Lambda_7^3\), and the \((11,5,2)\) biplane and its complement are the unique minimizers in \(\Lambda_{11}^5\) and \(\Lambda_{11}^6\).
  • Minc (1978) noted that some matrices in \(\Lambda_7^3\) that are not configurations have the same permanent as the Fano plane.

Our progress so far

The first open cases are \(\Lambda_{13}^4\) and \(\Lambda_{13}^9\), where the configuration is unique: the projective plane \(\mathrm{PG}(2,3)\), with permanent \(3852\), and its complement, whose permanent we computed exactly as \(64{,}803{,}969\). A switch replaces a \(2\times2\) submatrix \(\bigl(\begin{smallmatrix}1&0\\0&1\end{smallmatrix}\bigr)\) by \(\bigl(\begin{smallmatrix}0&1\\1&0\end{smallmatrix}\bigr)\) or back, preserving all line sums.

  • Local optimality at \(v=13\). Every non-configuration in \(\Lambda_{13}^4\) within two switches of \(\mathrm{PG}(2,3)\) has permanent at least \(3884\), and every non-configuration within two switches of its complement has permanent at least \(64{,}839{,}709\). Both bounds are attained.
  • Local optimality of other designs. Every one-switch neighbour has strictly larger permanent than the design for the parameters \((11,5,2)\), \((11,6,3)\), \((13,4,1)\), \((13,9,6)\), \((15,7,3)\), \((15,8,4)\), \((16,6,2)\) and \((16,10,6)\).
  • Minimizers are not unique. All \(84\) one-switch neighbours of the Fano plane are non-configurations with the minimum permanent \(24\) in \(\Lambda_7^3\), so the conjecture cannot be strengthened to uniqueness.
  • Search evidence. Searches in \(\Lambda_{13}^4\), \(\Lambda_{13}^9\) and around designs up to order \(21\) found no counterexample. This is evidence, not a proof.

References

  1. H. J. Ryser, Matrices of zeros and ones, Bull. Amer. Math. Soc. 66 (1960), 442–464. doi:10.1090/S0002-9904-1960-10494-6
  2. M. Marcus and H. Minc, Permanents, Amer. Math. Monthly 72 (1965), 577–591. doi:10.1080/00029890.1965.11970575
  3. H. Minc, Permanents, Encyclopedia of Mathematics and its Applications 6, Addison-Wesley, 1978.
  4. I. M. Wanless, On Minc’s sixth conjecture, Linear and Multilinear Algebra 55 (2007), 57–63. doi:10.1080/03081080600562670