A lower bound on the maximum permanent in &Lambda_n^k

Let P_n^k be the maximum value achieved by the permanent over &Lambda_n^k, the set of (0,1)-matrices of order n with exactly k ones in each row and column. Bregman proved that P_n^k≤ k!^n/k. It is shown here that P_n^k≥ k!^tr! where n=tk+r and 0≤ r<k. From this simple bound we derive that (P_n^k)^1/n is asymptotically equal to k!^1/k whenever k=o(n) and deduce a number of structural results about matrices which achieve P_n^k. These include restrictions for large n and k on the number of components which may be drawn from &Lambda_k+c^k for a constant c≥1.

Our results can be directly applied to maximisation problems dealing with the number of extensions to Latin rectangles or the number of perfect matchings in regular bipartite graphs.

Click here to download the whole paper.

Last modified: Mon May 31 16:45:27 EST 2004

A lower bound on the maximum permanent in &Lambdank

A lower bound on the maximum permanent in &Lambda_n^k