Publication date
November 2003
DOI Publisher
Published by Elsevier Inc. ISSN
0024-3795Abstract
AbstractLet Pnk be the maximum value achieved by the permanent over Λnk, the set of (0,1)-matrices of order n with exactly k ones in each row and column. Brègman 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∼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 Λk+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
Add to ORKG