---
res:
bibo_abstract:
- 'Eigenvalues associated to graphs are a well-studied subject. In particular the
spectra of the adjacency matrix and of the Laplacian of random graphs G(n, p)
are known quite precisely. We consider generalizations of these matrices to simplicial
complexes of higher dimensions and study their eigenvalues for the Linial-Meshulam
model X k(n, p) of random k-dimensional simplicial complexes on n vertices. We
show that for p = Ω(log n/n), the eigenvalues of both, the higher-dimensional
adjacency matrix and the Laplacian, are a.a.s. sharply concentrated around two
values. In a second part of the paper, we discuss a possible higherdimensional
analogue of the Discrete Cheeger Inequality. This fundamental inequality expresses
a close relationship between the eigenvalues of a graph and its combinatorial
expansion properties; in particular, spectral expansion (a large eigenvalue gap)
implies edge expansion. Recently, a higher-dimensional analogue of edge expansion
for simplicial complexes was introduced by Gromov, and independently by Linial,
Meshulam and Wallach and by Newman and Rabinovich. It is natural to ask whether
there is a higher-dimensional version of Cheeger''s inequality. We show that the
most straightforward version of a higher-dimensional Cheeger inequality fails:
for every k > 1, there is an infinite family of k-dimensional complexes that
are spectrally expanding (there is a large eigenvalue gap for the Laplacian) but
not combinatorially expanding.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Anna
foaf_name: Gundert, Anna
foaf_surname: Gundert
- foaf_Person:
foaf_givenName: Uli
foaf_name: Uli Wagner
foaf_surname: Wagner
foaf_workInfoHomepage: http://www.librecat.org/personId=36690CA2-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-1494-0568
bibo_doi: 10.1145/2261250.2261272
dct_date: 2012^xs_gYear
dct_publisher: ACM@
dct_title: On Laplacians of random complexes@
...