## Abstract

Let Λ^{k} _{n} denote the set of (0, 1)-matrices of order n with exactly k ones in each row and column. Let J_{i} be such that Λ^{i} _{i} = {J_{i}} and for A ∈ Λ^{k} _{n} define Ā ∈ Λ^{n-k} _{n} by Ā = J_{n} - A. We are interested in the matrices in Λ^{k} _{n} which maximise the permanent function. Consider the sets Mn = {A ∈ Λ^{k} _{n}: per(A) ≥ per(B), for all B ∈ Λ^{k} _{n}}, M̄kn = {A ∈ Λ^{k} _{n}: per(Ā) ≥ per(B̄), for all B ∈ Λ^{k} _{n}}. For k fixed and n sufficiently large we prove the following results. 1. Modulo permutations of the rows and columns, every member of M^{k} _{n} ∪ M̄^{k} _{n} is a direct sum of matrices of bounded size of which fewer than k differ from J_{k}. 2. A ∈ M^{k} _{n} if and only if A ⊕ J_{k} ∈ M^{k} _{n+k}. 3. A ∈ M̄^{k} _{n} if and only if A ⊕ J_{k} ∈ M̄^{k} _{n+k}. 4. M3n = M̄3n if n ≡ 0 or 1 (mod3) but M3n ∩ M̄^{3} _{n} = ∅ if n ≡ 2(mod3). We also conjecture the exact composition of M̄^{k} _{n} for large n, which is equivalent to identifying regular bipartite graphs with the maximum number of 4-cycles.

Original language | English |
---|---|

Pages (from-to) | 191-205 |

Number of pages | 15 |

Journal | Discrete Mathematics |

Volume | 205 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 28 Jul 1999 |

Externally published | Yes |

## Keywords

- (0, 1)-matrices
- Permanent
- Regular bipartite graphs
- Rook polynomials