Eigenvalues and homology of flag complexes and vector representations of graphs
| dc.creator | Aharoni, R. | |
| dc.creator | Berger, E. | |
| dc.creator | Meshulam, R. | |
| dc.date | 2003-12-29 | |
| dc.date.accessioned | 2026-07-07T05:04:14Z | |
| dc.date.available | 2026-07-07T05:04:14Z | |
| dc.description | Let X(G) denote the flag complex of a graph G=(V,E) on n vertices. We study relations between the first eigenvalues of successive higher Laplacians of X(G). One consequence is the following result: Let λ_2(G) denote the second smallest eigenvalue of the Laplacian of G. If λ_2(G)> \frac{kn}{k+1} then the real k-th reduced cohomology group H^k(X(G)) is zero. 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 a Hall type theorem for systems of disjoint representatives in hypergraphs. | |
| dc.description | 14 pages | |
| dc.identifier | https://arxiv.org/abs/math/0312482 | |
| dc.identifier | http://arxiv.org/abs/math/0312482 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69726 | |
| dc.subject | Combinatorics | |
| dc.subject | 55U10 (primary) 05C69 (secondary) | |
| dc.title | Eigenvalues and homology of flag complexes and vector representations of graphs | |
| dc.type | text |