Spectrum and local weak convergence of sparse random uniform hypergraphs

Abstract

The notion of local weak convergence, or Benjamini--Schramm convergence, was introduced by Benjamini and Schramm. The local weak limit of sparse Erd\H os--Rényi graphs is the Galton--Watson measure with Poisson offspring almost surely. Recently, Adhikari, Kumar, and Saha showed that the line graph of sparse Linial--Meshulam complexes converges to the $d$-block Galton--Watson measure. We study a unified model: weighted line graphs of sparse $k$-uniform random hypergraphs on $n$ vertices. Let $H(n,k,p)$ be the $k$-uniform random hypergraph where each $k$-subset of $[n]$ is included as a hyperedge independently with probability $p$. For a $k$-uniform hypergraph $H=(V,E)$ and $1\le r\le k-1$, define the $r$-set weighted line graph $G_r(H)=({\mathcal{V}}_r,{\mathcal{E}}_r,w_H)$ by $${\mathcal{V}}_r=\left[\right(\genfrac{}{}{0ex}{}{n}{r}\left)\right],{\mathcal{E}}_r=\{\{\ddot{I}{„}_1,\ddot{I}{„}_2\}:\ddot{I}{„}_1,\ddot{I}{„}_2\in {\mathcal{V}}_r,\exists e\in E\text{ s.t. }\ddot{I}{„}_1,\ddot{I}{„}_2\subset e\},$$ with weight $w_H(\{\ddot{I}{„}_1,\ddot{I}{„}_2\})=|\{e\in E:\ddot{I}{„}_1,\ddot{I}{„}_2\subset e\}|$. In particular, $G_1(H_n)$ generalizes Erd\H os--Rényi graphs and $G_{k-1}(H_n)$ is the line graph of the Linial--Meshulam complex. We show that if $\left(\genfrac{}{}{0ex}{}{n-r}{k-r}\right)\to \hat{I}»$ as $n\to \infty$, then $G_r(H_n)$ converges locally to the $((\genfrac{}{}{0ex}{}{k}{r})-1)$-block Galton--Watson measure with $\mathrm{Poisson}(\hat{I}»)$ offspring almost surely. As a consequence, we obtain the limiting spectral distribution of the adjacency matrices of $G_r(H_n)$.

44 pages