Strongly Connected Orientations and Integer Lattices
摘要
Let \(D\,=\,(V,A)\) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper face F of P not contained in \(\{x:x_a=i\}\) for any \(a\in A,i\in \{0,1\}\) . We prove under a mild necessary condition that \(F\cap \{0,1\}^A\) contains an integral basis B, i.e., B is linearly independent, and any integral vector in the linear hull of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form a Hilbert basis. In proving the result, we develop a theory similar to Matching Theory for degree-constrained dijoins in bipartite digraphs. Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say \(\tau \) , is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any prime number \(p\,\ge \,2\) , a p-adic packing of dijoins of value \(\tau \) and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by \(F\cap \{0,1\}^A\) , where F is the face of P satisfying \(x(\delta ^+(U))=1\) for every minimum dicut \(\delta ^+(U)\) .