Foregger–Sinkhorn tie-point conjecture
Follow the latest progress by email.
For a permanent-minimizing matrix on a doubly stochastic face, does a zero entry with permanental cofactor exceeding the permanent have to be a tie point? The Foregger–Sinkhorn implication is tested on nearly decomposable supports.
Why it matters and what counts as progress
Why it matters: A global minimizer violating the implication would delimit a proposed structural rule for permanent minimization on stochastic faces.
What counts as progress: Prove the implication in further support classes or produce a full-face global minimizer violating it at a specified zero.
How the problem developed
- 1986 · Conjecture [1]
Thomas H. Foregger and Richard Sinkhorn Proposed a tie-point criterion for zeros of a nearly decomposable doubly stochastic matrix minimizing the permanent on a face.
- 1987 · Partial result [2]
Thomas H. Foregger Proved the criterion for faces whose associated bipartite graph is a complex, a restricted family of patterns.
- 13 Aug 2026 · Reported counterexample [3]
Yair Lavi Reported an exact order-eight counterexample to the conjecture.
AI contribution
A counterexample to the Foregger-Sinkhorn tie-point conjecture
An explicit 8×8 nearly decomposable support has a unique global permanent minimizer on its full doubly stochastic face. At a specified zero, the permanental cofactor exceeds the permanent although that zero is not a tie point, refuting the Foregger–Sinkhorn implication.
Sources
- Thomas H. Foregger and Richard Sinkhorn · On matrices minimizing the permanent on faces of the polyhedron of doubly stochastic matrices
- Thomas H. Foregger · Minimum permanents of multiplexes
- Yair Lavi · A counterexample to the Foregger–Sinkhorn tie-point conjecture
- Lavi, counterexample to the Foregger–Sinkhorn tie-point conjecture
Website timeline
Publication dates and editorial changes.
AI-assisted proof refutes the Foregger–Sinkhorn tie-point conjecture