math.CO — Combinatorics

Foregger's Conjecture on Minimum Permanents of Nearly Decomposable Doubly Stochastic Matrices

Contributed by Yair Lavi

We prove Foregger's conjecture: every nearly decomposable doubly stochastic matrix $A$ of order $n\ge2$ satisfies $\operatorname{per}A\ge 2^{1-n}$. Equality holds exactly for matrices obtained from $\tfrac12(I_n+P_n)$ by independent row and column permutations, where $P_n$ is a single-cycle permutation matrix. In fact, for every fixed nearly decomposable support whose bipartite graph is not a single cycle, the minimum permanent on its closed doubly stochastic face is strictly larger than $2^{1-n}$.