Complexes of Directed Graphs
Anders Björner, Volkmar Welker · SIAM Journal on Discrete Mathematics · 1999
Let P be a monotone property of directed graphs on n vertices, and let $\Delta_n^{P}$ denote the abstract simplicial complex whose simplices are the edge sets of graphs having property P. We prove the following: If "P = acyclic,' then $\Delta_n^{P}$ is homotopy equivalent to the (n-2)-sphere. If "P = not strongly connected,' then $\Delta_n^{P}$ has the homotopy type of a wedge of (n-1)! spheres of dimension 2n-4. The lattice of all posets on {1,2,...,n} plays an important role in the analysis. We also discuss some other properties of directed graphs from this point of view.