Strongly Connected Orientations and Integer Lattices

Let [Formula: see text] be a digraph whose underlying undirected graph is two-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 [Formula: see text] for any [Formula: see text]. We prove under a mild necessary condition that [Formula: see text] 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 [Formula: see text], is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture by finding for any prime number [Formula: see text], a p-adic packing of dijoins of value [Formula: see text] and of support size at most [Formula: see text]. We also prove that the all-ones vector belongs to the lattice generated by [Formula: see text], where F is the face of P satisfying [Formula: see text] for every dicut [Formula: see text] with minimum size. Funding: This research was supported by the Office of Naval Research [Grant N00014-22-1-2528] and the Engineering and Physical Sciences Research Council [Grant EP/X030989/1].