Let \(G = (V,E)\) be a \(d\)-regular graph with adjacency matrix \(\mathcal{A}(G)\), whose eigenvalues are \(\lambda _1(\mathcal{A}(G)) = d \ge \lambda _2(\mathcal{A}(G)) \ge \cdots \). The spectral expansion (spectral gap) of \(G\) is \(\lambda := \lambda _1(\mathcal{A}(G)) - \lambda _2(\mathcal{A}(G)) = d - \lambda _2(\mathcal{A}(G))\). \(G\) is a \(\lambda \)-spectral expander if its spectral expansion is at least \(\lambda \).

For a graph \(G = (V,E)\) let \(\operatorname {Aut}(G) \subset \mathcal{S}_{|V|}\) be its group of automorphisms. \(G\) is vertex transitive if for all \(u, v \in V\) there is an automorphism \(\sigma \in \operatorname {Aut}(G)\) with \(\sigma (u) = v\).

A graph assignment scheme corresponding to a graph \(G\) with \(n\) vertices and \(m\) edges is the matrix \(A \in \{ 0,1\} ^{n \times m}\) with \(A_{ij} = 1\) iff the \(j\)th edge of \(G\) has vertex \(i\) as an endpoint. Here the \(n\) vertices are the data blocks and the \(m\) edges are the machines, so each machine holds exactly two data blocks. Each block consists of \(\tfrac {dN}{2m}\) data points, the number of blocks is \(n = \tfrac {2m}{d}\), the computational load (points per machine) is \(\ell = \tfrac {dN}{m}\), and the replication factor is \(d = \tfrac {2m}{n}\), independent of block size. Results are stated in terms of the \(n \times m\) block-to-machine matrix.