# 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!^{t}r! 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