---
_id: '1282'
abstract:
- lang: eng
  text: 'We consider higher-dimensional generalizations of the normalized Laplacian
    and the adjacency matrix of graphs and study their eigenvalues for the Linial–Meshulam
    model Xk(n, p) of random k-dimensional simplicial complexes on n vertices. We
    show that for p = Ω(logn/n), the eigenvalues of each of the matrices are a.a.s.
    concentrated around two values. The main tool, which goes back to the work of
    Garland, are arguments that relate the eigenvalues of these matrices to those
    of graphs that arise as links of (k - 2)-dimensional faces. Garland’s result concerns
    the Laplacian; we develop an analogous result for the adjacency matrix. The same
    arguments apply to other models of random complexes which allow for dependencies
    between the choices of k-dimensional simplices. In the second part of the paper,
    we apply this to the question of possible higher-dimensional analogues of the
    discrete Cheeger inequality, which in the classical case of graphs relates the
    eigenvalues of a graph and its edge expansion. It is very natural to ask whether
    this generalizes to higher dimensions and, in particular, whether the eigenvalues
    of the higher-dimensional Laplacian capture the notion of coboundary expansion—a
    higher-dimensional generalization of edge expansion that arose in recent work
    of Linial and Meshulam and of Gromov; this question was raised, for instance,
    by Dotterrer and Kahle. We show that this most straightforward version of a higher-dimensional
    discrete Cheeger inequality fails, in quite a strong way: For every k ≥ 2 and
    n ∈ N, there is a k-dimensional complex Yn k on n vertices that has strong spectral
    expansion properties (all nontrivial eigenvalues of the normalised k-dimensional
    Laplacian lie in the interval [1−O(1/√1), 1+0(1/√1]) but whose coboundary expansion
    is bounded from above by O(log n/n) and so tends to zero as n → ∞; moreover, Yn
    k can be taken to have vanishing integer homology in dimension less than k.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Anna
  full_name: Gundert, Anna
  last_name: Gundert
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: Gundert A, Wagner U. On eigenvalues of random complexes. <i>Israel Journal
    of Mathematics</i>. 2016;216(2):545-582. doi:<a href="https://doi.org/10.1007/s11856-016-1419-1">10.1007/s11856-016-1419-1</a>
  apa: Gundert, A., &#38; Wagner, U. (2016). On eigenvalues of random complexes. <i>Israel
    Journal of Mathematics</i>. Springer. <a href="https://doi.org/10.1007/s11856-016-1419-1">https://doi.org/10.1007/s11856-016-1419-1</a>
  chicago: Gundert, Anna, and Uli Wagner. “On Eigenvalues of Random Complexes.” <i>Israel
    Journal of Mathematics</i>. Springer, 2016. <a href="https://doi.org/10.1007/s11856-016-1419-1">https://doi.org/10.1007/s11856-016-1419-1</a>.
  ieee: A. Gundert and U. Wagner, “On eigenvalues of random complexes,” <i>Israel
    Journal of Mathematics</i>, vol. 216, no. 2. Springer, pp. 545–582, 2016.
  ista: Gundert A, Wagner U. 2016. On eigenvalues of random complexes. Israel Journal
    of Mathematics. 216(2), 545–582.
  mla: Gundert, Anna, and Uli Wagner. “On Eigenvalues of Random Complexes.” <i>Israel
    Journal of Mathematics</i>, vol. 216, no. 2, Springer, 2016, pp. 545–82, doi:<a
    href="https://doi.org/10.1007/s11856-016-1419-1">10.1007/s11856-016-1419-1</a>.
  short: A. Gundert, U. Wagner, Israel Journal of Mathematics 216 (2016) 545–582.
date_created: 2018-12-11T11:51:07Z
date_published: 2016-10-01T00:00:00Z
date_updated: 2025-09-22T08:34:49Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/s11856-016-1419-1
external_id:
  arxiv:
  - '1411.4906'
  isi:
  - '000386356400002'
intvolume: '       216'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1411.4906
month: '10'
oa: 1
oa_version: Preprint
page: 545 - 582
publication: Israel Journal of Mathematics
publication_status: published
publisher: Springer
publist_id: '6034'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On eigenvalues of random complexes
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 216
year: '2016'
...