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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: January 2004 Revised: August 2004 Accepted: August 2004
Rights and permissions
About this article
Cite this article
Aharoni, R., Berger, E. & Meshulam, R. Eigenvalues and homology of flag complexes and vector representations of graphs. GAFA, Geom. funct. anal. 15, 555–566 (2005). https://doi.org/10.1007/s00039-005-0516-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00039-005-0516-9