Abstract
Let Λkn denote the set of (0, 1)-matrices of order n with exactly k ones in each row and column. Let Ji be such that Λii = {Ji} and for A ∈ Λkn define Ā ∈ Λn-kn by Ā = Jn - A. We are interested in the matrices in Λkn which maximise the permanent function. Consider the sets Mn = {A ∈ Λkn: per(A) ≥ per(B), for all B ∈ Λkn}, M̄kn = {A ∈ Λkn: per(Ā) ≥ per(B̄), for all B ∈ Λkn}. For k fixed and n sufficiently large we prove the following results. 1. Modulo permutations of the rows and columns, every member of Mkn ∪ M̄kn is a direct sum of matrices of bounded size of which fewer than k differ from Jk. 2. A ∈ Mkn if and only if A ⊕ Jk ∈ Mkn+k. 3. A ∈ M̄kn if and only if A ⊕ Jk ∈ M̄kn+k. 4. M3n = M̄3n if n ≡ 0 or 1 (mod3) but M3n ∩ M̄3n = ∅ if n ≡ 2(mod3). We also conjecture the exact composition of M̄kn 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 |