Geodesic
Maximising the permanent of \((0,1)\)-matrices and the number of extensions of Latin rectangles
The electronic journal of combinatorics, Tome 5 (1998)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $k\geq2$, $m\geq5$ and $n=mk$ be integers. By finding bounds for certain rook polynomials, we identify the $k\times n$ Latin rectangles with the most extensions to $(k+1)\times n$ Latin rectangles. Equivalently, we find the $(n-k)$-regular subgraphs of $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$ 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.
DOI : 10.37236/1349
Classification : 05B15, 05C70, 15A15, 15B36
Mots-clés : permanent, Latin rectangles, adjacency matrix, complete bipartite graph, rook polynomial 
@article{10_37236_1349,
     author = {B. D. McKay and I. M. Wanless},
     title = {Maximising the permanent of \((0,1)\)-matrices and the number of extensions of {Latin} rectangles},
     journal = {The electronic journal of combinatorics},
     year = {1998},
     volume = {5},
     doi = {10.37236/1349},
     zbl = {0887.05011},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1349/}
}
TY  - JOUR
AU  - B. D. McKay
AU  - I. M. Wanless
TI  - Maximising the permanent of \((0,1)\)-matrices and the number of extensions of Latin rectangles
JO  - The electronic journal of combinatorics
PY  - 1998
VL  - 5
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1349/
DO  - 10.37236/1349
ID  - 10_37236_1349
ER  - 
%0 Journal Article
%A B. D. McKay
%A I. M. Wanless
%T Maximising the permanent of \((0,1)\)-matrices and the number of extensions of Latin rectangles
%J The electronic journal of combinatorics
%D 1998
%V 5
%U http://geodesic.mathdoc.fr/articles/10.37236/1349/
%R 10.37236/1349
%F 10_37236_1349
B. D. McKay; I. M. Wanless. Maximising the permanent of \((0,1)\)-matrices and the number of extensions of Latin rectangles. The electronic journal of combinatorics, Tome 5 (1998). doi: 10.37236/1349

Cité par Sources :