Directed subgraph complexes (Q1773174)

Summary: Let \(G\) be a directed graph, and let \(\Delta^{ACY}_G\) be the simplicial complex whose simplices are the edge sets of acyclic subgraphs of \(G\). Similarly, we define \(\Delta^{NSC}_G\) to be the simplicial complex with the edge sets of not strongly connected subgraphs of \(G\) as simplices. We show that \(\Delta^{ACY}_G\) is homotopy equivalent to the \((n-1-k)\)-dimensional sphere if \(G\) is a disjoint union of \(k\) strongly connected graphs. Otherwise, it is contractible. If \(G\) belongs to a certain class of graphs, the homotopy type of \(\Delta^{NSC}_G\) is shown to be a wedge of \((2n-4)\)-dimensional spheres. The number of spheres can easily be read off the chromatic polynomial of a certain associated undirected graph. We also consider some consequences related to finite topologies and hyperplane arrangements.