Loose Laplacian spectra of random hypergraphs

2011/09/15 by Lu, Linyuan, Peng, Xing
#05C65 #05C80 #15B52 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1109.3433

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 V\choose s 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 passing through I and J if I∩ J=∅, and 0 if I∩ J\not=∅. The s-th Laplacian Ł^(s) of H is defined to be the normalized Laplacian of G^(s). The eigenvalues of \mathcal L^(s) are listed as λ^(s)₀, λ^(s)₁,..., λ^(s)_n\choose s-1 in non-decreasing order. Let λ^(s)(H)=max_i\not=0\|1-λ^(s)_i|\. The parameters λ^(s)(H) and λ^(s)₁(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, p(1-p)≫ \fraclog⁴ nn^r-s, and 1-p≫ (log n)/(n²), we prove that almost surely λ^(s)(H^r(n,p))≤ (s)/(n-s)+ (3+o(1))√\frac1-pn-s\choose r-sp. We also prove that the empirical distribution of the eigenvalues of Ł^(s) for H^r(n,p) follows the Semicircle Law if p(1-p)≫ \fraclog^1/3 nn^r-s and 1-p≫ \fraclog nn^2+2r-2s.

Related

• High-ordered Random Walks and Generalized Laplacians on Hypergraphs
• On the spectrum of hypergraphs
• Spectrum and local weak convergence of sparse random uniform hypergraphs
• Random Walks on Hypergraphs with Edge-Dependent Vertex Weights
• Eigenvalue Distribution of Large Weighted Random Sparse Uniform q-Hypergraphs