Doubly stochastic matrices and dicycle covers and packings in Eulerian digraphs (Q1816947): Difference between revisions

This paper studies the problem of describing the convex hull \(\Omega_n^0\) of all nonidentity permutation matrices of order \(n\) by a system of linear inequalities. Such a description was first given by \textit{A. B. Cruse} [Linear Algebra Appl. 26, 45-57 (1979; Zbl 0412.15015)]. While this description involves infinitely many inequalities, it does provide an efficiently testable criterion for membership in \(\Omega_n^0\): a doubly stochastic matrix \(W\) is in \(\Omega_n^0\) if and only if \(\min\{\sum_{i,j}W_{i,j}X_{i,j}:X\in P_n\}\geq 1\), where \(P_n\) is a polytope defined by a system of inequalities of size polynomial in \(n\). The authors use this to provide an alternative criterion for membership in \(\Omega_n^0\) in terms of dicycle covers as follows. A dicycle cover in a digraph is an assignment of nonnegative values to arcs such that the sum of values on each dicycle it at least \(1\). They show that a doubly stochastic matrix \(W\) is in \(\Omega_n^0\) if and only if the minimum weight of a dicycle cover in the weighted digraph naturally associated with \(W\) is at least \(1\). Using this criterion, they show that the complete description of \(\Omega_n^0\) for \(n\leq 6\) by transitive tournament inequalities due to \textit{R. A. Brualdi} and \textit{G.-S. Hwang} [Linear Algebra Appl. 172, 151-168 (1992; Zbl 0755.15011)], is valid if and only if \(n\leq 6\). They also show that weighted Eulerian digraphs on \(n\leq 6\) vertices always have an integral minimum weight dicycle cover, and prove a min-max relation for such graphs.