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

Let Λ_n^k 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ⁱ={J_i} and for A in Λ_n^k define comp{A} in Λ_n^n-k by comp{A}=J_n-A. We are interested in the matrices in Λ_n^k which maximise the permanent function. Consider the sets

M_n^k={A in Λ_n^k: per(A)≥per(B), for all B in Λ_n^k},

C_n^k={A in Λ_n^k: per(comp{A})≥per(comp{B}), for all B in Λ_n^k}.

For k fixed and n sufficiently large we prove the following results.

Modulo permutations of the rows and columns, every member of M_n^k union C_n^k is a direct sum of matrices of bounded size of which fewer than k differ from J_k.
A in M_n^k if and only if A direct sum J_k is in M_n+k^k.
A in C_n^k if and only if A direct sum J_k is in C_n+k^k.
M_n³=C_n³ if n=0 or 1 (mod 3) but M_n³ intersect C_n³ is the emptyset if n=2 (mod 3).

We also conjecture the exact composition of C_n^k for large n, which is equivalent to identifying regular bipartite graphs with the maximum number of 4-cycles.

Click here to download the whole paper.