On the Homotopy Type of Multipath Complexes

A multipath in a directed graph is a disjoint union of paths. The multipath complex of a directed graph (Formula presented.) is the simplicial complex whose faces are the multipaths of (Formula presented.). We compute Euler characteristics, and associated generating functions, of the multipath complexes of directed graphs from certain families, including transitive tournaments and complete bipartite graphs. We show that if (Formula presented.) is a linear graph, polygon, small grid or transitive tournament, then the homotopy type of the multipath complex of (Formula presented.) is always contractible or a wedge of spheres. We introduce a new technique for decomposing directed graphs into dynamical regions, which allows us to simplify the homotopy computations.