--- _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.' 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. Israel Journal of Mathematics. 2016;216(2):545-582. doi:10.1007/s11856-016-1419-1 apa: Gundert, A., & Wagner, U. (2016). On eigenvalues of random complexes. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-016-1419-1 chicago: Gundert, Anna, and Uli Wagner. “On Eigenvalues of Random Complexes.” Israel Journal of Mathematics. Springer, 2016. https://doi.org/10.1007/s11856-016-1419-1. ieee: A. Gundert and U. Wagner, “On eigenvalues of random complexes,” Israel Journal of Mathematics, 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.” Israel Journal of Mathematics, vol. 216, no. 2, Springer, 2016, pp. 545–82, doi:10.1007/s11856-016-1419-1. 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: 2021-01-12T06:49:36Z day: '01' department: - _id: UlWa doi: 10.1007/s11856-016-1419-1 intvolume: ' 216' 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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 216 year: '2016' ...