Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum (Q1301841)

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.