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∈A,i∈{0,1}. We prove under a mild necessary condition that F∩{0,1} A contains an integral basisB, 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 τ, is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any prime number p≥2, a p-adic packing of dijoins of value τ and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by F∩{0,1} A, where F is the face of P satisfying x(δ +(U))=1 for every minimum dicut δ +(U).