Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-27T18:24:33.813Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Permanent of a Certain Class of (0, 1)-Matrices

Published online by Cambridge University Press:  20 November 2018

D. J. Hartfiel  and
J. W. Crosby
D. J. Hartfiel
Affiliation:
Texas A & M University, College Station, Texas
J. W. Crosby
Affiliation:
University of Houston, Houston, Texas
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In [3, p. 77] Ryser notes the importance of the minimum of the permanent function on the class of (0, 1)-matrices having exactly k ones in each row and column. In [4] a lower bound was found for the minimum of the permanent on the class Λn of n × n (0, 1)-matrices with exactly three l's in each row and column. The purpose of our work is to improve this result, in particular we show that minA ∊ Λn (per A) ≥ 3(n-1).

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 14 , Issue 4 , December 1971 , pp. 507 - 511
Copyright
Copyright © Canadian Mathematical Society 1971

References

1. Hartfiel, D. J., A simplified form for nearly reducible and nearly decomposable matrices, Proc. Amer. Math. Soc. 24 (1970), 388-393.Google Scholar
2. Mine, H., On lower bounds for permanents of (0, 1) matrices, Proc. Amer. Math. Soc. 22 (1969), 117-123.Google Scholar
3. Ryser, H. J., Combinatorial mathematics, Carus Monograph No. 14, Amer. Math. Soc. 1963.Google Scholar
4. Sinkhorn, R., Concerning a conjecture of Marshall Hall, Proc. Amer. Math. Soc. 21 (1969), 197-201.Google Scholar