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.

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