A lower bound on the maximum permanent in
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