Directed subgraph complexes
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.
- Simplicial schemes
- Directed graphs and substitutions
- Complexes of directed trees
- Combinatorial triangulations of homology spheres
- scientific article; zbMATH DE number 177202 (Why is no real title available?)
- Complexes of Directed Graphs
- scientific article; zbMATH DE number 7324139 (Why is no real title available?)
- On the homotopy type of multipath complexes
- Directed trees in a string, real polynomials with triple roots, and chain mails
This page was built for publication: Directed subgraph complexes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1773174)
