Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum
type: Item
instance of: scholarly article
title: Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum
zbMATH Open document ID: 0952.15007
DOI: 10.1016/S0012-365X(99)00048-5
published in: Discrete Mathematics
publication date: 2001-01-03T00:00:00Z
review text: This paper deals with upper bounds for the permanent of a class of matrices that has important applications to various enumeration problems. Let \(\Lambda_n^k\) denote the set of (0,1)-matrices of order \(n\) with exactly \(k\) ones in each row and column. For some \(A \in \Lambda_n^k\) define \(\overline{A} = J_n - A,\) where \(J_n\) denotes the \(n \times n\)-matrix all of whose entries are one. Furthermore, let \(M_n^k = \{ A \in \Lambda_n^k : \text{per} (A) \geq \text{per} (B) \text{ for all } B \in \Lambda_n^k\},\) and \(\overline{M}_n^k = \{ A \in \Lambda_n^k :\text{per} (\overline{A}) \geq \text{per} (\overline{B}) \text{ for all } B \in \Lambda_n^k\}.\) Among others, the following results are established for \(k\) fixed and \(n\) sufficiently large: (a) \(A \in M_n^k\) if and only if \(A \oplus J_k \in M_{n+k}^k;\) (b) \(A \in \overline{M}_n^k\) if and only if \(A \oplus J_k \in \overline{M}_{n+k}^k;\) (c) \(M_n^3 = \overline{M}_n^3\) if \(n \equiv 0\) or \(1\pmod 3\) but \(M_n^3 \cap \overline{M}_n^3 = \emptyset\) if \(n \equiv 2\pmod 3\). Finally, the author mentions a conjecture which is equivalent to identifying regular bipartite graphs with the maximum number of 4-cycles.
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 15A45
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 15B36
zbMATH DE Number: 1334686
zbMATH Keywords: permanents
zbMATH Keywords: \((0,1)\)-matrices
zbMATH Keywords: rook polynomials
zbMATH Keywords: regular bipartite graphs
zbMATH Keywords: enumeration problems
author: Ian M. Wanless
MaRDI profile type: Publication
cites work: Q5558293
cites work: Q4044717
cites work: Maximum permanents of matrices of zeros and ones
cites work: Hermite polynomials and a duality relation for matchings polynomials
cites work: Asymptotic enumeration of Latin rectangles
cites work: Maximising the permanent of \((0,1)\)-matrices and the number of extensions of Latin rectangles
cites work: The maximum permanent in
cites work: Theory of permanents 1978–1981
cites work: Counting 1-factors in regular bipartite graphs
Wikidata QID: Q127884386
description: scientific article; zbMATH DE number 1334686