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 |