Spectral expansion of random sum complexes

Abstract

Let $G$ be a finite abelian group of order $n$ and let ${\Delta }_{n-1}$ denote the $(n-1)$-simplex on the vertex set $G$. The sum complex $X_{A,k}$ associated to a subset $A\subset G$ and $k<n$, is the $k$-dimensional simplicial complex obtained by taking the full $(k-1)$-skeleton of ${\Delta }_{n-1}$ together with all $(k+1)$-subsets $\sigma \subset G$ that satisfy ${\sum }_{x\in \sigma }x\in A$. Let $C^{k-1}(X_{A,k})$ denote the space of complex valued $(k-1)$-cochains of $X_{A,k}$. Let $L_{k-1}:C^{k-1}(X_{A,k})\to C^{k-1}(X_{A,k})$ denote the reduced $(k-1)$-th Laplacian of $X_{A,k}$, and let ${\mu }_{k-1}(X_{A,k})$ be the minimal eigenvalue of $L_{k-1}$. It is shown that for any $k\ge 1$ and $\epsilon >0$ there exists a constant $c(k,\epsilon )$ such that if $A$ is a random subset of $G$ of size $m=\lceil c(k,\epsilon )\log n\rceil$, then ${\mu }_{k-1}(X_{A,k})>(1-\epsilon )m$ asymptotically almost surely.

12 pages, one figure