Symmetric groups and expander graphs. (Q2458878): Difference between revisions

A finite graph \(\Gamma\) with vertex set \(V(\Gamma)\) is called an \(\varepsilon\)-expander for some \(0<\varepsilon<1\) if for any subset \(A\subseteq V(\Gamma)\) of size at most \(|V(\Gamma)|/2\) we have \(|\partial(A)|>\varepsilon|A|\), where \(\partial(A)\) denotes the set of vertices of \( V(\Gamma)\setminus A\) connected by an edge with a vertex in \(A\); the largest such \(\varepsilon\) is called the expanding constant of \(\Gamma\). The main result of the present paper is Theorem 2. For every \(n\) there exists a generating set \(S_n\) (of size at most \(L\)) of the alternating group \(\text{Alt}(n)\) such that the Cayley graphs \(\mathcal C(\text{Alt}(n),S_n)\) form a family of \(\varepsilon\)-expanders. Here, \(L\) and \(\varepsilon>0\) are some universal constants. Similarly there exists a generating set \(\widetilde{S_n}\) of the symmetric group \(\text{Sym}(n)\) with the same property. The proof is based on the concept of Kazhdan property \(T\) and (relative) Kazhdan constant.