Maximising the permanent of \((0,1)\)-matrices and the number of extensions of Latin rectangles
type: Item
instance of: scholarly article
title: Maximising the permanent of \((0,1)\)-matrices and the number of extensions of Latin rectangles
zbMATH Open document ID: 0887.05011
author: Brendan D. McKay
author: Ian M. Wanless
published in: The Electronic Journal of Combinatorics
publication date: 1998-02-18T00:00:00Z
full work available at URL: https://eudml.org/doc/119365
full work available at URL: v5i1r11.html
review text: 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)].
Mathematics Subject Classification ID: 05B15
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 15B36
zbMATH DE Number: 1119076
zbMATH Keywords: permanent
zbMATH Keywords: Latin rectangles
zbMATH Keywords: adjacency matrix
zbMATH Keywords: complete bipartite graph
zbMATH Keywords: rook polynomial
reviewed by: Arbind Kumar Lal
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1119076