Spectra of adjacency and Laplacian matrices of Erdős-Rényi hypergraphs

Abstract

We study adjacency and Laplacian matrices of Erdős-Rényi $r$-uniform hypergraphs on $n$ vertices with hyperedge inclusion probability $p$, in the setting where $r$ can vary with $n$ such that $r/n\to c\in [0,1)$. Adjacency matrices of hypergraphs are contractions of adjacency tensors and their entries exhibit long range correlations. We show that under the Erdős-Rényi model, the expected empirical spectral distribution of an appropriately normalised hypergraph adjacency matrix converges weakly to the semi-circle law with variance $(1-c{)}^2$ as long as $\frac{d_{\avg}}{r^7} \to \infty$, where $d_{\avg} = \binom{n-1}{r-1} p$. In contrast with the Erdős-Rényi random graph ($r=2$), two eigenvalues stick out of the bulk of the spectrum. When $r$ is fixed and $d_{\avg} \gg n^{r - 2} \log^4 n$, we uncover an interesting Baik-Ben Arous-Péché (BBP) phase transition at the value $r=3$. For $r\in \{2,3\}$, an appropriately scaled largest (resp. smallest) eigenvalue converges in probability to $2$ (resp. $-2$), the right (resp. left) end point of the support of the standard semi-circle law, and when $r\ge 4$, it converges to $\sqrt{r-2}+\frac{1}{\sqrt{r-2}}$ (resp. $-\sqrt{r-2}-\frac{1}{\sqrt{r-2}}$). Further, in a Gaussian version of the model we show that an appropriately scaled largest (resp. smallest) eigenvalue converges in distribution to $\frac{c}{2}\zeta +[\frac{c^2}{4}{\zeta }^2+c(1-c){]}^{1/2}$ (resp. $\frac{c}{2}\zeta -[\frac{c^2}{4}{\zeta }^2+c(1-c){]}^{1/2}$), where $\zeta$ is a standard Gaussian. We also establish analogous results for the bulk and edge eigenvalues of the associated Laplacian matrices.