1 Preliminaries and library prerequisites
For a finite simple graph \(H\) on vertex set \(V\), the adjacency matrix \(A_H\) is the \(V \times V\) matrix with \((A_H)_{uv} = 1\) if \(u\) and \(v\) are adjacent and \(0\) otherwise. It is a real symmetric matrix, hence has real eigenvalues. (Recalled so later nodes can speak of its eigenvalues.)
Let \(A\) be a real symmetric \(n \times n\) matrix with eigenvalues \(\mu _0, \dots , \mu _{n-1}\) (with multiplicity). Then for every natural number \(k\), \(\operatorname {Tr}(A^{k}) = \sum _{i=0}^{n-1} \mu _i^{k}\).
If \(\varphi \) is a concave function and \(Y\) an integrable random variable then \(\mathbb {E}(\varphi (Y)) \le \varphi (\mathbb {E}(Y))\); dually for convex \(\varphi \) the inequality reverses. We use it for \(\varphi (y) = y^{1/2m}\) (concave on \([0,\infty )\)): \(\mathbb {E}(Y^{1/2m}) \le (\mathbb {E}(Y))^{1/2m}\).
Let \(F_0, F_1, \dots , F_d\) be a martingale with \(|F_{i+1} - F_i| \le b_i\) for all \(i\). Then for every \(t {\gt} 0\), \(\operatorname {Pr}\! \left(|F_d - F_0| \ge t\right) \le 2\exp \! \big(-t^2 / (2\sum _i b_i^2)\big)\).
A character of a finite abelian group \(A\) is a homomorphism \(\chi : A \to \mathbb {C}^{\times }\) into the multiplicative group of complex numbers. The characters of \(A\) form a group isomorphic to \(A\) (Pontryagin duality), there are exactly \(|A|\) of them, and the trivial character sends every element to \(1\).
Every finite abelian group \(A\) is isomorphic to a direct sum of cyclic groups, \(A \cong \mathbb {Z}_{p_1} \oplus \mathbb {Z}_{p_2} \oplus \dots \oplus \mathbb {Z}_{p_k}\). Consequently every nontrivial character of \(A\) is a product of characters of the cyclic summands, at least one of which is nontrivial.
Let \(G\) be a finite group and \(S \subseteq G\) a set of elements. The (undirected) Cayley graph \(X(G,S)\) has vertex set \(G\) and edge set the unordered pairs \(\{ \{ g, gs\} : g \in G,\ s \in S\} \). It is a regular graph of degree \(|S \cup S^{-1}| \le 2|S|\).
For every finite group \(G\) and \(S \subseteq G\), the graph \(X(G,S)\) is regular of degree \(d = |S \cup S^{-1}|\) and is vertex transitive: for any two vertices \(g, h \in G\) the left translation \(x \mapsto h g^{-1} x\) is a graph automorphism sending \(g\) to \(h\).
Each vertex \(g\) is adjacent precisely to \(\{ gs : s \in S \cup S^{-1}\} \), which has \(|S \cup S^{-1}| = d\) elements, so the graph is \(d\)-regular. For vertex transitivity, fix \(g,h\) and let \(\sigma (x) = hg^{-1}x\). Then \(\sigma (g) = h\), and \(\{ x, xs\} \) is an edge iff \(\{ \sigma (x), \sigma (x)s\} = \{ hg^{-1}x, hg^{-1}xs\} \) is an edge, since \(\sigma (xs) = \sigma (x)s\). Hence \(\sigma \) is an automorphism, and as \(g,h\) were arbitrary the automorphism group acts transitively on vertices.
For a graph \(H\) let \(\mu _{1}[H]\) denote the second largest eigenvalue, in absolute value, of the adjacency matrix \(A_H\). If \(H\) is \(d\)-regular, its normalized adjacency matrix is the doubly stochastic matrix \(A^{*}_H = \tfrac 1d A_H\), and \(\mu _{1}^{*}[H]\) denotes the second largest eigenvalue, in absolute value, of \(A^{*}_H\). Clearly \(\mu _{1}^{*}[H] = \tfrac 1d \mu _{1}[H]\).
A graph \(H\) is called a \(c\)-expander if for every set of vertices \(S\), \(|\Gamma (S)| {\gt} c\, |S|\, (1 - |S|/|H|)\), where \(\Gamma (S)\) is the set of all neighbours of \(S\).
A regular graph \(\Gamma \) of constant degree is an \(\varepsilon (\delta )\)-expander whenever the second largest eigenvalue, in absolute value, of its normalized adjacency matrix is at most \(1 - \delta \). (Quantitatively, a normalized second eigenvalue of \(1-\delta \) yields an expansion constant \(\varepsilon (\delta )\).)