The Holens-Dokovic conjecture on permanents fails

Let A be a doubly stochastic matrix of order n and σ_i(A) the sum of the order i subpermanents of A. The HD conjecture says in σ_i(A)≥(n-i+1)²σ_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.

Click here to download the whole paper.