Eigenvalues and homology of flag complexes and vector representations of graphs
By R. Aharoni, Eli Berger, R. Meshulam. 2003
56 citations recorded by the source corpus.
Abstract.The flag complex of a graph G = (V, E) is the simplicial complex X(G) on the vertex set V whose simplices are subsets of V which span complete subgraphs of G. We study relations between the first eigenvalues of successive higher Laplacians of X(G). One consequence is the following:Theorem:Let λ2(G) denote the second smallest eigenvalue of the Laplacian of G. If$$\lambda_{2}(G)\,>\,\frac{k}{k+1}|V|$$then$$ \ifmmode\expandafter\tilde\else\expandafter\~\fi{H}^{k} {\left( {X(G);\mathbb{R}} \right)} = 0.$$Applications include a lower bound on the homological connectivity of the independent sets complex I(G), in terms of a new graph domination parameter Γ(G) defined via certain vector representations of G. This in turns implies Hall type theorems for systems of disjoint representatives in hypergraphs.
Subfields: Computational Theory and Mathematics, Geometry and Topology, Physiology
View Paper: https://www.semanticscholar.org/paper/9a140de45ef8b6135f2dde443611987cc3f6f936
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Geometry and Topology
In Physiology
Citations in the corpus
- Sharp vanishing thresholds for cohomology of random flag complexes (2012, methodology): “I first learned of applications of Garland’s method in topological combinatorics from [1], where Aharoni, Berger, and Meshulam establish a global analogue of the cohomology vanishing theorem for flag complexes.”