A lower bound on the maximum permanent in Λnk

✍ Scribed by Ian M. Wanless

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 147 KB
• Volume: 373
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(02)00715-2

✦ Synopsis

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