Expansion of product replacement graphs (Q858141)

From MaRDI portal
Revision as of 21:20, 19 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Expansion of product replacement graphs
scientific article

    Statements

    Expansion of product replacement graphs (English)
    0 references
    0 references
    0 references
    8 January 2007
    0 references
    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)].
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    expanders
    0 references
    Cayley graphs
    0 references
    product replacement graph
    0 references
    0 references