A lower bound on the maximum permanent in &Lambdank

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