The Holens-Doković conjecture on permanents fails!

Research output: Contribution to journalArticleResearchpeer-review

7 Citations (Scopus)

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 languageEnglish
Pages (from-to)273-285
Number of pages13
JournalLinear Algebra and Its Applications
Volume286
Issue number1-3
DOIs
Publication statusPublished - 1 Jan 1999
Externally publishedYes

Cite this