Answers are grounded in this paper and cite their sources.
This research reveals lattice structures in integer points related to strongly connected orientations in directed graphs, suggesting new theoretical implications.
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].
No takes yet. Share an insight, caveat, or question.
Abdi et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: