Dependencies

For every \(1 {\gt} \varepsilon {\gt} 0\) there exists a \(c(\varepsilon ) {\gt} 0\) such that the following holds. Let \(G\) be a group of order \(n\) and let \(S\) be a random set of \(c(\varepsilon )\log _2 n\) elements of \(G\). Then the Cayley graph \(X(G,S)\) is an \(\varepsilon \)-expander almost surely, i.e. the probability that it is such an expander tends to \(1\) as \(n \to \infty \).

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.

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 \(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|\).

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\).

For the random Cayley graph \(X(G,S)\) with \(|S| = c\log _2 n\) elements chosen randomly in \(G\), let \(P_{2m}\) denote the probability that a fixed walk of length \(2m\) in the graph (starting at a given vertex, with prescribed sequence of generator-steps) is closed, i.e. returns to its start.

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\).

An \([l,m,\varepsilon ]\)-code is a binary linear code of length \(l\) and dimension \(m\) in which the Hamming weight of each nontrivial codeword lies between \(\tfrac {1-\varepsilon }{2}\, l\) and \(\tfrac {1+\varepsilon }{2}\, l\).

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]\).

Let \(G\) be a finite abelian group and \(S \subseteq G\). The eigenvalues of the adjacency matrix of \(X(G,S)\) are exactly the \(|G|\) quantities

one for each character \(\chi \) of \(G\).

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)\).

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\).

Let \(A\) be a finite abelian group, \(\chi \) a fixed nontrivial character, and \(\sigma \) a uniformly random element of \(A\). Then

For \(S \subseteq \mathbb {Z}_2^{m}\) let \(B = B(S)\) be the \(m \times |S|\) binary matrix whose columns are the elements of \(S\), and put \(|S| = l\). The Cayley graph \(H = X(\mathbb {Z}_2^{m}, S)\) satisfies \(|\mu _{1}[H]| \le \varepsilon l\) if and only if the Hamming weight of every nonzero codeword of the linear code generated by the rows of \(B\) lies between \(\tfrac {1-\varepsilon }{2}\, l\) and \(\tfrac {1+\varepsilon }{2}\, l\); equivalently, iff that code is an \([l,m,\varepsilon ]\)-code.

The second largest eigenvalue, in absolute value, of any regular graph with \(n\) vertices and degree \(d\) is at least \(2\sqrt{d-1}\, \big(1 - O(\log ^2 d / \log ^2 n)\big)\), and this estimate is essentially optimal (achieved by Ramanujan graphs and by random regular graphs).

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 )\).)

Over the probability space of all normalized adjacency matrices of Cayley graphs \(X(G,S)\) with \(|S| = c\log _2 n\) random elements, for every positive integer \(m\), writing \(n = |G|\),

Let \(U\) be a random word of length \(2t\) in the free monoid \(M_{2d}\) generated by \(d\) letters and their inverses. Then

where an identity sequence is one that reduces to the empty word in the free group \(F_d\).

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}\).

With \(l(w) = 2m(1 - \ln \ln 2m / \ln 2m)\),

Let \(G\) be a group and let \(S\) be a random set of \(d\) elements in \(G\). Put \(\mu _{1}= \mu _{1}[X(G,S)]\). Then for every \(c {\gt} 0\),

In the dynamic process producing the random walk, let \(A\) be the event that the reduced word \(W\) in the free group \(F_{c\log _2 n}\) has length \(l(W) {\lt} l(w) := 2m(1 - \ln \ln 2m / \ln 2m)\). Then

Let \(B\) be the event that the reduced word \(W\) has length at least \(2m(1 - \ln \ln 2m / \ln 2m)\) and no letter appears exactly once in it. Then, writing \(l(W)\) for the reduced length,

where \(l(W) \ge 2m(1 - \ln \ln 2m / \ln 2m)\).

Let \(C\) be the event that neither \(A\) nor \(B\) holds, yet after assigning to each letter a random element of \(G\) the reduced word evaluates to the identity. Then

A binary linear code of length \(l\) and minimum distance at least \(\delta l/2\), with \(2^{m}\) codewords, satisfies the volume bound

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}\).

Let \(A\) be a real symmetric matrix with eigenvalues \(|\mu _0| \ge |\mu _1| \ge \dots \ge |\mu _{n-1}|\). Then for every natural number \(m\),

For every fixed \(n\) and \(\delta {\gt} 0\) there is a constant \(c = c(\delta , n)\) such that if \(G_q = \mathrm{GL}(n,q)\), \(S_q \subseteq G_q\), and the family of Cayley graphs \(\{ X(G_q, S_q)\} \) is a family of \(\delta \)-expanders, then \(|S_q| \ge c\log |G_q|\).

For every \(1 {\gt} \delta {\gt} 0\) there is a \(c(\delta ) {\gt} 0\) such that the following holds. Let \(K\) be a complete graph on \(n\) vertices whose edges are coloured by \(n - 1\) colours so that each colour class is a perfect matching. Let \(H\) be the subgraph of \(K\) consisting of all edges whose colours belong to a randomly chosen set of \(c(\delta )\log _2 n\) colours. Then \(\mathbb {E}(|\mu _{1}[H]|) {\lt} (1-\delta )\, c(\delta )\log _2 n\).

Suppose \(G = \mathbb {Z}_2^{m}\) and \(X(G,S)\) is a Cayley graph of \(G\) whose second largest eigenvalue in absolute value is at most \((1-\delta )|S|\). Then

For every fixed \(\delta {\gt} 0\) there is a constant \(c = c(\delta ) {\gt} 0\) such that the following holds: if \(A\) is an abelian group of order \(n\) and \(X(A,S)\) is a \(\delta \)-expander, then \(|S| \ge c\log _2 n\).

There exists an absolute constant \(c {\gt} 0\) such that for every fixed \(\varepsilon {\gt} 0\) and every \(m\) one can describe explicitly a Cayley graph \(H = X(\mathbb {Z}_2^{m}, S_m)\) with \(|S_m| \le c\, \tfrac {1}{\varepsilon ^{3}}\, m\ \big(= c\, \tfrac {1}{\varepsilon ^{3}} \log _2 |\mathbb {Z}_2^{m}|\big)\), so that \(|\mu _{1}[H]| \le \varepsilon |S_m|\).

There exists an absolute constant \(c {\gt} 0\) such that for every \(\varepsilon {\gt} 0\) and every \(m\) one can describe explicitly a Cayley graph \(H = X(\mathbb {Z}_2^{m}, S_m)\) with \(l = |S_m| \le c\, m^2/\varepsilon ^2\), so that \(|\mu _{1}[H]| \le \varepsilon |S_m| = O(\sqrt{lm})\). Explicitly: take a prime \(l \ge (2m/\varepsilon + 1)^2\) and define \(B = (b_{ij})\) for \(1 \le i \le m\), \(1 \le j \le l\) by \(b_{ij} = 0\) if \(i - j\) is a quadratic residue in the field \(\mathbb {Z}_l\), and \(b_{ij} = 1\) otherwise.

There exists an absolute constant \(c {\gt} 0\) such that for every \(1 {\gt} \varepsilon {\gt} 0\) and every \(m\) there exists a Cayley graph \(H = X(\mathbb {Z}_2^{m}, S_m)\) with \(l = |S_m| \le c\, m/\varepsilon ^2\), so that \(|\mu _{1}[H]| \le \varepsilon |S_m| = O(\sqrt{l\sqrt{m}})\).

For every abelian group \(G\) of order \(n\) and for every \(l\), if \(S\) is a set of \(l\) random members of \(G\) then almost surely \(|\mu _{1}[X(G,S)]| \le O(\sqrt{l\sqrt{\log n}})\).

There exists an absolute constant \(\gamma {\gt} 0\) such that for every \(m \le l \le 2^{\gamma m}\), the second largest eigenvalue of any Cayley graph \(X(\mathbb {Z}_2^{m}, S)\) with \(|S| = l\) is at least \(\Omega (\sqrt{lm}/\sqrt{\log l})\). In particular, for large \(m\) no such graph \(H\) with degree a small power of the number of vertices can be Ramanujan (i.e. satisfy \(|\mu _{1}[H]| \le 2\sqrt{l-1}\)).

For every abelian group \(G\) of order \(n\) and for every \(l = \Omega (\log n / \log \log n)\), if \(S\) is an arbitrary set of \(l\) members of \(G\) then

For every \(1 {\gt} \delta {\gt} 0\) there is a \(c(\delta ) {\gt} 0\) such that the following holds. Let \(G\) be a group of order \(n\) and let \(S\) be a set of \(c(\delta )\log _2 n\) random elements of \(G\). Then

Moreover for \(0 {\lt} \delta {\lt} 1 - \tfrac 1e\) one may take \(c(\delta ) \le (1 + o(1))\, 2e^4\ln 2 / [(1-\delta )e - 1]^2\).

For each small \(\delta {\gt} 0\) there exists an \(\varepsilon = O(\delta \log (1/\delta ))\) such that for any abelian group \(A\) of order \(n\) the Cayley graph \(X(A,S)\) of \(A\) with respect to a (multi-)subset \(S\) of \((1+\varepsilon )\log _2 n\) random elements (not necessarily distinct) satisfies \(|\mu _{1}^{*}[X(A,S)]| \le 1 - \delta \) almost surely (with probability tending to \(1\) as \(n \to \infty \)).