Integral matrices with given row and column sums (Q2760994)

Let \(Q\) be an \(m\times n\) matrix with nonnegative integral entries and \((r_1,\ldots ,r_m)\), \((s_1,\ldots ,s_n)\) two nonnegative integral vectors with the same sum. Does there exist a nonnegative integral \(m\times n\) matrix \(A\) having row sums \(r_i\), column sums \(s_j\), and satisfying \(a_{ij}\leq q_{ij}\) for every \(i\) and \(j\)? By the maxflow-mincut theorem, \(A\) exists iff certain \(2^{m+n}\) inequalities among the parameters \(q_{ij}\), \(r_i\), and \(s_j\) are satisfied. Generalizing theorems of Gale and Ryser, Anstee and Chen, the author proves a theorem containing a hierarchy of weaker conditions for \(Q\) and \(s_j\), under which the existence of \(A\) is equivalent to (in \(n)\) polynomially many cut inequalities. For example, if NEWLINE\[NEWLINE\sum _{i=1}^m(q_{ij}-q_{ik})^+\leq s_j-s_k+1\quad \text{for}\quad 1\leq j<k<nNEWLINE\]NEWLINE, then \(A\) exists if and only if NEWLINE\[NEWLINE\sum _{i=1}^m \Bigl(r_i-\sum _{j\in J}q_{ij} \Bigr)^{+}\leq \sum _{j\not \in J}s_jNEWLINE\]NEWLINE for every initial interval \(J=\{1,2,\ldots ,h\}\) (\(x^{+}=x\) for positive \(x\) and \(0\) else).