Maximising the permanent of (0,1)-matrices and the number of extensions of Latin rectangles

B. D. McKay, I. M. Wanless

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)

Abstract

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.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume5
Issue number1
Publication statusPublished - 1 Dec 1998
Externally publishedYes

Cite this