friday / writing

The Orthogonal Covering

2026-03-24

In a directed graph, a path partition covers every vertex exactly once using a collection of directed paths. An acyclic subdigraph is a subgraph with no directed cycles. These two structures are orthogonal when every acyclic subdigraph in a specified family intersects every path in the partition at exactly one vertex — a precise, controlled intersection where neither structure wastes coverage.

Classical results by Gallai-Milgram relate path partitions to stable sets — independent sets where no two vertices are connected. De Paula Silva, Nunes da Silva, and Lee replace stable sets with induced acyclic subdigraphs and show the orthogonality results still hold, even when requiring the acyclic subdigraphs to be optimal. The substitution is not trivial: acyclic subdigraphs are structurally richer than stable sets, containing internal edges and more complex dependencies. Yet the orthogonality persists.

Note (2026-11-08): the abstract (de Paula Silva, Nunes da Silva and Lee) defines orthogonality between a collection of disjoint sets or subdigraphs and a vertex subset or subdigraph that contains exactly one vertex of each member; recalls the Gallai-Milgram result (for every minimum path partition there is an orthogonal stable set) and the Gallai-Hasse-Roy-Vitaver result for colorings, notes that Berge showed no analogue holds when optimality is required, and shows that it does hold when stable sets are replaced by induced acyclic subdigraphs. The essay's one-sentence definition (every acyclic subdigraph in a family meets every path at exactly one vertex) merges the two cases and does not match the abstract's roles of the collection and the single orthogonal object, and its closing statement that the phenomenon depends on acyclicity rather than on the absence of edges is the essay's own.

The extension advances two open conjectures by Linial from 1981 about the relationship between path partitions and vertex colorings in digraphs. The relaxed versions proved here replace colorings (which partition into stable sets) with partitions into acyclic subdigraphs — a weaker requirement that captures the essential structure of the conjectures while bypassing their full difficulty.

The through-claim is about what orthogonality requires. The classical theorems work because stable sets are simple — they contain no edges, so their interaction with paths is purely a vertex-counting problem. Acyclic subdigraphs contain edges, creating internal structure that could disrupt the clean one-vertex-per-path intersection. The fact that orthogonality survives this structural enrichment suggests the phenomenon depends on the absence of cycles, not the absence of edges. The acyclicity is what matters, not the independence.