9 Alon’s generalization
Let \(G_{n,d}\) be a \(d\)-regular graph on \(n\) nodes with second-largest eigenvalue \(\lambda \). Let \(S\) be a subset of the vertices of \(G_{n,d}\) of size \(\gamma n\). Then the number of paths of length \(k\) contained in the subgraph induced by \(S\) in \(G_{n,d}\) is at most
For all integers \(k\ge 2\) and all \(\epsilon \) such that \(1-kH(\epsilon ){\gt}0\), there exists a polynomial-time constructible family of linear codes of rate \(1-kH(\epsilon )\) and minimum relative distance arbitrarily close to \(\epsilon ^{1+1/(k-1)}\), for which a circuit of size \(O(n\log n)\) and logarithmic depth will decode some \(\Omega (\epsilon ^{1+1/(k-1)})\) fraction of error. Moreover this circuit can be simulated in linear time on a sequential machine.
(Sketch, following Theorem 38.) Use the graphs of Theorem 18. Form a code on the \(k\)-path-vertex incidence graph of \(G_{n,p+1}\): the large side is all paths of length \(k\) in the graph, the small side is its vertices, and a path is connected to the vertices along it (the case \(k=1\) recovers the edge-vertex construction of Theorem 38). Take the constraints to be a Gilbert–Varshamov code (Lemma 37); for large block length \(p+1\) there exist linear codes of rate \(r\) and relative distance \(\epsilon \) with \(r \le 1-H(\epsilon )\). Replacing Lemma 5 by Lemma 39 in the distance and round-progress arguments, and letting the eigenvalue term \(\lambda /d \to 0\), shows that no word of weight up to \(\epsilon ^{(k+1)/k}\) can be a codeword and that a decoding round shrinks the corrupt set; since \(\lambda /d\) never reaches \(0\) the relative distance only comes arbitrarily close to \(\epsilon ^{1+1/(k-1)}\). The rate is \(1-kH(\epsilon )\) because there are \(nd^k\) variables of degree \(k\) and \(n\) constraints of degree \(kd^k\).