Random Balanced Cayley Complexes

Abstract

Let $G$ be a finite group of order $n$ and for $1\le i\le k+1$ let $V_i=\{i\}\times G$. Viewing each $V_i$ as a $0$-dimensional complex, let $Y_{G,k}$ denote the simplicial join $V_1\ast \cdots \ast V_{k+1}$. For $A\subset G$ let $Y_{A,k}$ be the subcomplex of $Y_{G,k}$ that contains the $(k-1)$-skeleton of $Y_{G,k}$ and whose $k$-simplices are all $\{(1,x_1),\dots ,(k+1,x_{k+1})\}\in Y_{G,k}$ such that $x_1\cdots x_{k+1}\in A$. Let $L_{k-1}$ denote the reduced $(k-1)$-th Laplacian of $Y_{A,k}$, acting on the space $C^{k-1}(Y_{A,k})$ of real valued $(k-1)$-cochains of $Y_{A,k}$. The $(k-1)$-th spectral gap ${\mu }_{k-1}(Y_{A,k})$ of $Y_{A,k}$ is the minimal eigenvalue of $L_{k-1}$. The following $k$-dimensional analogue of the Alon-Roichman theorem is proved: Let $k\ge 1$ and $\epsilon >0$ be fixed and let $A$ be a random subset of $G$ of size $m=\lceil \frac{10k^2\log D}{{\epsilon }^2}\rceil$ where $D$ is the sum of the degrees of the complex irreducible representations of $G$. Then \[ {\rm Pr}\big[~μ_{k-1}(Y_{A,k}) < (1-ε)m~\big] =O\left(\frac{1}{n}\right). \]

18 pages