Abstract
Let A be a doubly stochastic matrix of order n and σi(A) the sum of the order i subpermanents of A. The Holens-Doković Conjecture says in σi(A) ≥ (n - i + l)2 σi-1 (A) for each i = 1,2,⋯,n. There is a natural counterpart of this conjecture for (0, 1)-matrices with constant line sum k. We show this associated conjecture holds when k ≤ 2, k ≥ n - 2, i ≤ n/k + 1 or i ≤ 5 but that it fails in general because it (wrongly) asserts a polynomial bound on the ratio of near perfect to perfect matchings in k-regular bipartite graphs.
| Original language | English |
|---|---|
| Pages (from-to) | 273-285 |
| Number of pages | 13 |
| Journal | Linear Algebra and Its Applications |
| Volume | 286 |
| Issue number | 1-3 |
| DOIs | |
| Publication status | Published - 1 Jan 1999 |
| Externally published | Yes |
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver