The path-missing and path-free complexes of a directed graph

Abstract

We study two simplicial complexes arising from a directed graph $G=(V,E)$ with two chosen vertices $s$ and $t$: the *path-free complex*, consisting of all subsets $F\subseteq E$ that contain no path from $s$ to $t$, and the *path-missing complex*, its Alexander dual. Using discrete Morse theory, we prove that both complexes have well-behaved homotopy types -- either contractible or homotopy-equivalent to spheres.

49 pages (37 main, 10 appendix, 2 bib). v4 corrects further typos and updates references. Comments welcome!