A lower bound on the maximum permanent in Λnk

Research output: Contribution to journalConference articleResearchpeer-review

9 Citations (Scopus)

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 languageEnglish
Pages (from-to)153-167
Number of pages15
JournalLinear Algebra and Its Applications
Volume373
Issue numberSUPPL.
DOIs
Publication statusPublished - 1 Nov 2003
Externally publishedYes
EventCombinatorial Matrix Theory Conference (POSTECH) - Pohang, Korea, South
Duration: 14 Jan 200217 Jan 2002

Keywords

  • (0,1) matrix
  • Bregman bound
  • Latin rectangle
  • Merriell's conjecture
  • Permanent
  • Regular bipartite graph

Cite this