Complexes of directed trees and independence complexes
From MaRDI portal
Abstract: The theory of complexes of directed trees was initiated by Kozlov to answer a question by Stanley, and later on, results from the theory were used by Babson and Kozlov in their proof of the Lovasz conjecture. We develop the theory and prove that complexes on directed acyclic graphs are shellable. A related concept is that of independence complexes: construct a simplicial complex on the vertex set of a graph, by including each independent set of vertices as a simplex. Two theorems used for breaking and gluing such complexes are proved and applied to generalize results by Kozlov. A fruitful restriction is anti-Rips complexes: a subset P of a metric space is the vertex set of the complex, and we include as a simplex each subset of P with no pair of points within distance r. For any finite subset P of mathbb{R} the homotopy type of the anti-Rips complex is determined.
Recommendations
- Complexes of directed trees
- Complexes of directed trees of complete multipartite graphs
- Complexes of trees and nested set complexes
- Independent arborescences in directed graphs
- Complexity of independency and cliquy trees
- Shellability of complexes of directed trees
- On directed tree realizations of degree sets
- Complexes of Directed Graphs
- scientific article; zbMATH DE number 6694457
- Independence complexes and incidence graphs
Cites work
- scientific article; zbMATH DE number 1344784 (Why is no real title available?)
- scientific article; zbMATH DE number 863503 (Why is no real title available?)
- A general homotopy complementation formula.
- A short proof of a conjecture on the connectivity of graph coloring complexes
- A simple proof for folds on both sides in complexes of graph homomorphisms
- Chessboard Complexes and Matching Complexes
- Complexes of directed trees
- Domination numbers and homology
- Extremal problems for transversals in graphs with bounded degree
- Hard squares with negative activity and rhombus tilings of the plane
- Homotopy properties of greedoids
- Independence complexes of claw-free graphs
- Inequalities on well-distributed point sets on circles
- Morse theory for cell complexes
- On the independence complex of square grids
- Proof of the Lovász conjecture
- Shellable Nonpure Complexes and Posets. I
- The roots of the independence polynomial of a clawfree graph
- The topology of the independence complex
- WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences
Cited in
(31)- Divisors on graphs, binomial and monomial ideals, and cellular resolutions
- Matching complexes of polygonal line tilings
- A note on independence complexes of chordal graphs and dismantling
- Splittings of independence complexes and the powers of cycles
- General polygonal line tilings and their matching complexes
- Certain homology cycles of the independence complex of grids
- The cyclomatic number of a graph and its independence polynomial at \(- 1\)
- Matching complexes of small grids
- Directed trees in a string, real polynomials with triple roots, and chain mails
- A dual independence complex
- On the homology of the real complement of the \(k\)-parabolic subspace arrangement
- Cores of simplicial complexes
- Independence complexes of chordal graphs
- Boolean formulae, hypergraphs and combinatorial topology
- Homotopy type of circle graph complexes motivated by extreme Khovanov homology
- Matching and independence complexes related to small grids
- Independence complexes of \((n \times 4)\) and \((n \times 5)\)-grid graphs
- The cubical matching complex revisited
- A simplicial complex is uniquely determined by its set of discrete Morse functions
- A functorial Dowker theorem and persistent homology of asymmetric networks
- On the homology of independence complexes
- Star clusters in independence complexes of graphs
- Dominance complexes and vertex cover numbers of graphs
- Dominance complexes, neighborhood complexes and combinatorial Alexander duals
- Perfect matching complexes of honeycomb graphs
- The facet ideals of matching complexes of line graphs
- Matching complexes of trees and applications of the matching tree algorithm
- Weighted sheaves and homology of Artin groups
- Matching trees for simplicial complexes and homotopy type of devoid complexes of graphs
- Complexity of simplicial homology and independence complexes of chordal graphs
- Orphan complexes of neighborhood anti-Sperner graphs
This page was built for publication: Complexes of directed trees and independence complexes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1025954)
