Expansion of product replacement graphs (Q858141): Difference between revisions

The explicit construction of expander graphs goes back to the work of \textit{G. A. Margulis} [Probl. Peredachi Inf. 9, No. 4, 71--80 (1973; Zbl 0312.22011)], and \textit{A. Lubotzky, R. Phillips} and \textit{P. Sarnak} [Combinatorica 8, No. 3, 261--277 (1988; Zbl 0661.05035)]. Here we can see a different approach, when expander graphs arise from merely group properties. The product replacement graph \(\Gamma_k(G)\) is the following. The vertices of \(\Gamma_k(G)\) are the \(k\)-tuples of generators \(\{g_1,\dots, g_k\}\) of the group \(G\). For \((i, j)\), \(1 \leq i, j \leq k\), \(i \not = j\) there is an edge corresponding to the \(4k(k-1)\) transformations \(L_{i, j}^{\pm}\) and \(R_{i, j}^{\pm}\) as: \[ R_{i, j}^{\pm} : (g_1, \dots, g_i, \dots, g_k) \mapsto (g_1, \dots, g_ig_j^{\pm 1}, \dots, g_k), \] \[ L_{i, j}^{\pm} : (g_1, \dots, g_i, \dots, g_k) \mapsto (g_1, \dots, g_ig_j^{\pm 1}, \dots, g_k). \] The main theorem of the paper is that the expansion coefficient of the product replacement graph \(\Gamma_k(G)\) can be bounded by the minimal expansion coefficient of a Cayley graph of \(G\) with \(k\) generators. While to spell out the theorem needs lots of technicalities, it has a nice consequences. One of those: If the sequence of groups \(\{\text{PLS}(2, p),\;p-\text{prime}\}\) have universal expansion with \(m=4\) generators then the sequence of graphs \(\{\Gamma_k(\text{PLS}(2, p)), p-\text{prime}\}\) form an expander family for any fixed \(k \geq 3\). The result gives the theoretical basis for the heuristic used for generating a random element in a finite group, see in \textit{J. D. Lafferty} and \textit{D. Rockmore} [Exp. Math. 1, No. 2, 115--139 (1992; Zbl 0773.65091)].