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

I. M. Wanless*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

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 languageEnglish
Pages (from-to)191-205
Number of pages15
JournalDiscrete Mathematics
Volume205
Issue number1-3
DOIs
Publication statusPublished - 28 Jul 1999
Externally publishedYes

Fingerprint

Dive into the research topics of 'Maximising the permanent and complementary permanent of (0,1)-matrices with constant line sum'. Together they form a unique fingerprint.

Cite this