Maximising the permanent of \((0,1)\)-matrices and the number of extensions of Latin rectangles (Q1379135): Difference between revisions

Suppose \(k\geq 2\), \(m\geq 5\) and \(n = mk\) are integers. By obtaining bounds for certain rook polynomials, the authors identify the \(k \times n\) Latin rectangels that have the most extensions to \((k+1) \times n\) Latin rectangles. Equivalently, they find the \((n-k)\)-regular subgraphs of the complete bipartite graph \(K_{n,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,\) the authors solve the above problem for \(k=2\). Some computational results are also obtained which should be helpful in the formulation of the problem for general \(n\) and \(k\). The results also partially settle two open problems of \textit{Henryk Minc} and conjectures of \textit{D. Merriel} [Linear Multilinear Algebra 9, 81-91 (1980; Zbl 0438.15009)], and \textit{C. D. Godsil} and \textit{B. D. Mckay} [J. Comb. Theory, Ser. B 48, No. 1, 19-44 (1990; Zbl 0687.05010)].