  We consider higher-dimensional generalizations of the normalized Laplacian
and the adjacency matrix of graphs 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=\Omega(\log n/n)$, the eigenvalues of
these 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 higher-dimensional Laplacian spectra
capture the notion of coboundary expansion - a generalization of edge expansion
that arose in recent work of Linial and Meshulam and of Gromov. We show that
this most straightforward version of a higher-dimensional discrete Cheeger
inequality fails, in quite a strong way: For every $k\geq 2$ and $n\in
\mathbb{N}$, there is a $k$-dimensional complex $Y^k_n$ 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/\sqrt{n}),1+O(1/\sqrt{n})]$) but whose coboundary expansion is bounded
from above by $O(\log n/n)$ and so tends to zero as $n\rightarrow \infty$;
moreover, $Y^k_n$ can be taken to have vanishing integer homology in dimension
less than $k$.
