Maximising the permanent of (0,1) matrices and the number of extensions of Latin rectangles
Let k≥2, m≥5 and n=mk be integers. By finding bounds for
certain rook polynomials, we identify the k×n Latin rectangles
with the most extensions to (k+1)×n Latin rectangles.
Equivalently, we find the (n-k)-regular subgraphs of Kn,n which
have the greatest number of perfect matchings, and the (0,1)-matrices
with exactly k zeroes in every row and column which maximise the
permanent. Without the restriction on n being a multiple of k we
solve the above problem (and the corresponding minimisation problem) for
k=2. We also provide some computational results for small values of
n and k.
Our results partially settle two open problems of Minc and conjectures
by Merriell, and Godsil and McKay.