Foregger–Sinkhorn tie-point conjecture

← Minc’s list

Minc’s list · Conjecture 41

Foregger–Sinkhorn tie-point conjecture

Disproved by us arXiv preprint, August 2026

Posed by
Foregger and Sinkhorn
First posed
1986

Statement

Posed by T. H. Foregger and R. Sinkhorn in 1986, after they found counterexamples to an earlier conjecture of Minc about the same faces; it is Conjecture 41 in Minc’s 1987 survey.

Conjecture 41. Let \(\Omega_n\) be the set of \(n\times n\) doubly stochastic matrices, and for a set \(Z\) of positions let \(\Omega_n(Z)=\{S\in\Omega_n : s_{ij}=0 \text{ for all } (i,j)\in Z\}\). If \(A\) is a nearly decomposable matrix minimizing the permanent on \(\Omega_n(Z)\) and \((i,j)\in Z\), then

\[ \operatorname{per}A(i\mid j)>\operatorname{per}A \]

implies that \((i,j)\) is a tie point for \(A\).

Here \(A(i\mid j)\) is \(A\) with row \(i\) and column \(j\) deleted. A matrix is nearly decomposable if it is fully indecomposable but replacing any one of its nonzero entries by \(0\) makes it partly decomposable. Following Hartfiel, a zero position \((i,j)\) of such an \(A\) is a tie point if, after \((i,j)\) is made nonzero, deleting any original nonzero entry of \(A\) still leaves a partly decomposable pattern.

Resolution

We disproved the conjecture with an exact counterexample of order \(8\). On a nearly decomposable pattern \(D_8\) with \(19\) nonzero positions, the whole face \(\Omega(D_8)\) has a unique permanent minimizer \(A_\beta\), where \(\beta\in(0.59,0.6)\) is the real root of \(7\beta^3-13\beta^2+12\beta-4=0\). With \(Z\) the zero positions of \(D_8\) and \((i,j)=(1,5)\),

\[ \operatorname{per}A_\beta(1\mid 5)-\operatorname{per}A_\beta>\frac{2047}{240100}>0, \]

yet \((1,5)\) is not a tie point: once it is made nonzero, the original entry at \((4,5)\) can be deleted and the pattern stays fully indecomposable. The minimizer, the cofactor inequality and the failure of the tie-point condition are all verified exactly. We do not claim that eight is the smallest possible order.

Before this, Foregger had proved the conjecture in 1987 for faces whose bipartite graphs are complexes, two special vertices joined by internally disjoint paths; the counterexample lies outside that class.

Read our paper → arXiv:2608.13025 ↗

References

  1. T. H. Foregger and R. Sinkhorn, On matrices minimizing the permanent on faces of the polyhedron of the doubly stochastic matrices, Linear and Multilinear Algebra 19 (1986), 395–397. doi:10.1080/03081088608817734
  2. H. Minc, Minimum permanents of doubly stochastic matrices with prescribed zero entries, Linear and Multilinear Algebra 15 (1984), 225–243. doi:10.1080/03081088408817592
  3. D. J. Hartfiel, On constructing nearly decomposable matrices, Proc. Amer. Math. Soc. 27 (1971), 222–228. doi:10.1090/S0002-9939-1971-0268062-4
  4. T. H. Foregger, Minimum permanents of multiplexes, Linear Algebra Appl. 87 (1987), 197–211. doi:10.1016/0024-3795(87)90167-4
  5. Y. Lavi, A counterexample to the Foregger–Sinkhorn tie-point conjecture, preprint (2026). arXiv:2608.13025