Abstract
Let 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 P nk≥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.
Original language | English |
---|---|
Pages (from-to) | 153-167 |
Number of pages | 15 |
Journal | Linear Algebra and Its Applications |
Volume | 373 |
Issue number | SUPPL. |
DOIs | |
Publication status | Published - 1 Nov 2003 |
Externally published | Yes |
Event | Combinatorial Matrix Theory Conference (POSTECH) - Pohang, Korea, South Duration: 14 Jan 2002 → 17 Jan 2002 |
Keywords
- (0,1) matrix
- Bregman bound
- Latin rectangle
- Merriell's conjecture
- Permanent
- Regular bipartite graph