Loose laplacian spectra of random hypergraphs

Abstract

Abstract Let H = ( V, E ) be an r ‐uniform hypergraph with the vertex set V and the edge set E . For 1 ≤ s ≤ r /2, we define a weighted graph G ( s ) on the vertex set \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}${V\choose s}$\end{document} as follows. Every pair of s ‐sets I and J is associated with a weight w ( I, J ), which is the number of edges in H containing I and J if I ∩ J = ∅︁, and 0 if I ∩ J ≠ ∅︁. The s ‐th Laplacian \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$\mathcal L^{(s)}$\end{document} of H is defined to be the normalized Laplacian of G ( s ) . The eigenvalues of \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$\mathcal L^{(s)}$\end{document} are listed as \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$\lambda^{(s)}_0, \lambda^{(s)}_1, \ldots, \lambda^{(s)}_{{n\choose s}-1}$\end{document} in non‐decreasing order. Let \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$\bar\lambda^{(s)}(H)=\max_{i\neq 0}\{|1-\lambda^{(s)}_i|\}$\end{document} . The parameters \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$\bar\lambda^{(s)}(H)$\end{document} and λ ( H ), which were introduced in our previous paper, have a number of connections to the mixing rate of high‐ordered random walks, the generalized distances/diameters, and the edge expansions. For 0 < p < 1, let H r ( n, p ) be a random r ‐uniform hypergraph over [ n ] := {1, 2, …, n }, where each r ‐set of [ n ] has probability p to be an edge independently. For 1 ≤ s ≤ r /2, \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$p(1-p)\gg \frac{\log^4 n}{n^{r-s}}$\end{document} , and \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$1-p\gg \frac{\log n}{n^2}$\end{document} , we prove that almost surely We also prove that the empirical distribution of the eigenvalues of \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$\mathcal L^{(s)}$\end{document} for H r ( n, p ) follows the Semicircle Law if \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$p(1-p)\gg \frac{\log^{1/3} n}{n^{r-s}}$\end{document} and \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$1-p\gg \frac{\log n}{n^{2+2r-2s}}$\end{document} . © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012