Complexes of Directed Graphs
A property \(P\) of graphs is called monotone if it is preserved under the deletion of edges. Let \(\Delta^P_n\) denote the simplicial complex whose simplices are edge sets of \(n\)-vertex graphs having a monotone property \(P\). Topological properties of complexes of undirected graphs recently have been studied in a number of papers (see references in [Topology 38, No. 2, 271-299 (1999; Zbl 0936.57002)]) motivated by the theory of Vassiliev invariants in knot theory. In the paper under review complexes of directed graphs are studied. The main results are: Theorem 1.1. Let \(P\) mean the property of a digraph to be acyclic, i.e. to contain no direct cycles. Then the complex \(\Delta^P_n\) is homotopy equivalent to the \((n-2)\)-dimensional sphere. Theorem 1.2. Let \(P\) mean the property not to be strongly connected. The complex \(\Delta^P_n\) has the homotopy type of a wedge of \((n-1)!\) spheres of dimension \(2n-4\). Complexes of some other classes of digraphs (in particular, directed matchings) along with some remarks on the action of the symmetric group on the homology are also considered.
- Directed subgraph complexes
- scientific article; zbMATH DE number 1522572
- scientific article; zbMATH DE number 177202
- Homomorphism complexes, reconfiguration, and homotopy for directed graphs
- Unit ball graph homology
- Complexes of connected graphs
- Homotopy theory for digraphs
- Topology of matching, chessboard, and general bounded degree graph complexes
- scientific article; zbMATH DE number 3980021
- Complexes of directed trees of complete multipartite graphs
- Cycle-free chessboard complexes and symmetric homology of algebras
- Complexes of directed trees and independence complexes
- Directed graphs and substitutions
- Laplacian simplices associated to digraphs
- Directed subgraph complexes
- Complexes of directed trees
- Topology of bounded-degree graph complexes.
- Complexes of tournaments, directionality filtrations and persistent homology
- A simplicial complex is uniquely determined by its set of discrete Morse functions
- Combinatorial and topological aspects of path posets, and multipath cohomology
- Complexes of directed trees of complete multipartite graphs
- Directed Graphs and the Jacobi-Trudi Identity
- scientific article; zbMATH DE number 177202 (Why is no real title available?)
- Complexes of connected graphs
- scientific article; zbMATH DE number 1522572 (Why is no real title available?)
- Plane graphs with acyclic complex
- scientific article; zbMATH DE number 5879503 (Why is no real title available?)
- On efficient sparse integer matrix Smith normal form computations
- On the homotopy type of multipath complexes
- Monotone cohomologies and oriented matchings
- Torsion in the matching complex and chessboard complex
This page was built for publication: Complexes of Directed Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4699168)
