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
- 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
- scientific article; zbMATH DE number 1344784 (Why is no real title available?)
- scientific article; zbMATH DE number 863503 (Why is no real title available?)
- 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
(34)- Weighted sheaves and homology of Artin groups
- Homotopy type of circle graph complexes motivated by extreme Khovanov homology
- The cyclomatic number of a graph and its independence polynomial at - 1
- Matching complexes of small grids
- The facet ideals of matching complexes of line graphs
- Matching complexes of trees and applications of the matching tree algorithm
- Matching complexes of polygonal line tilings
- A functorial Dowker theorem and persistent homology of asymmetric networks
- A note on independence complexes of chordal graphs and dismantling
- A simplicial complex is uniquely determined by its set of discrete Morse functions
- Matching and independence complexes related to small grids
- Matching trees for simplicial complexes and homotopy type of devoid complexes of graphs
- Divisors on graphs, binomial and monomial ideals, and cellular resolutions
- A dual independence complex
- Star clusters in independence complexes of graphs
- Splittings of independence complexes and the powers of cycles
- On the homology of the real complement of the \(k\)-parabolic subspace arrangement
- On the homology of independence complexes
- The cubical matching complex revisited
- Orphan complexes of neighborhood anti-Sperner graphs
- General polygonal line tilings and their matching complexes
- Independence complexes of \((n \times 4)\) and \((n \times 5)\)-grid graphs
- Perfect matching complexes of honeycomb graphs
- Dominance complexes and vertex cover numbers of graphs
- Dominance complexes, neighborhood complexes and combinatorial Alexander duals
- Complexity of simplicial homology and independence complexes of chordal graphs
- On geometric realizations of the extreme Khovanov homology of pretzel links
- Directed trees in a string, real polynomials with triple roots, and chain mails
- Boolean formulae, hypergraphs and combinatorial topology
- On the homotopy type of the polyhedral join over the independence complex of a forest
- Helly number, domination and homology
- Cores of simplicial complexes
- Certain homology cycles of the independence complex of grids
- Independence complexes of chordal 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)
