6 Necessity of expansion (Appendix I)

Theorem 30 Theorem 24: necessity of expansion

Let \(d{\gt}c\), and let \(B\) be a bipartite graph between \(n\) variables of degree \(c\) and \((c/d)n\) constraints of degree \(d\) such that the simple sequential decoding algorithm successfully decodes all sets of at most \(\alpha n\) errors in \(\mathcal{C}(B,\mathcal{P})\). Then every set of \(\alpha n\) variables must have at least

\[ \alpha n\left(1 + \frac{2\, \frac{c-1}{2d}}{3+\frac{c-1}{2d}}\right) \]

neighbours.

Proof ▶

Case \(c\) even. Every flip changes the parity of each incident constraint, so flipping a variable changes the number of unsatisfied constraints by an even amount; whenever the algorithm flips a variable the number of unsatisfied constraints decreases by at least \(2\). Since the algorithm corrects \(\alpha n\) corrupt variables it must reduce the count by at least \(2\alpha n\), so every word of weight \(\alpha n\) is unsatisfied in at least \(2\alpha n\) constraints; hence every set of \(\alpha n\) variables has at least \(2\alpha n\) neighbours, and because \(d{\gt}c\) this exceeds the displayed bound. So the even case is done.

Case \(c\) odd. Now a flip can decrease the count of unsatisfied constraints by \(1\). At minimum every set of \(\alpha n\) variables induces at least \(\alpha n\) unsatisfied constraints, which alone only gives expansion by a factor \({\gt}1\). Consider what must happen for the algorithm to be in a state with \(\alpha n\) corrupt variables and no flip available that decreases the count by more than \(1\). Each corrupt variable must have at least \((c-1)/2\) of its edges in satisfied constraints; since each satisfied constraint has at most \(d\) incoming edges, there are at least \(\alpha n(c-1)/2d\) satisfied neighbours. Together with the \(\alpha n\) unsatisfied constraints, the \(\alpha n\) variables have at least \(\alpha n\bigl(1+(c-1)/2d\bigr)\) neighbours.

On the other hand, if the algorithm decreases the count by more than \(1\), it must decrease by at least \(3\) (parity, \(c\) odd). For a word of weight \(\alpha n\), suppose the algorithm flips \(\beta \alpha n\) variables that decrease the count by only \(1\) before it flips a variable that decreases it by \(3\). Accounting for both kinds of step (and the possible overlap between the \(3\beta \alpha n\) previously-flipped constraints and the extra \((1-\beta )\alpha n\, (c-1)/2d\)), the original \(\alpha n\) variables must have had at least

\[ \Bigl(1+\tfrac {c-1}{2d}\Bigr)(1-\beta )\alpha n + 3\beta \alpha n \]

neighbours. This bound is strictly decreasing in \(\beta \), while the previous paragraph’s bound is strictly increasing in \(\beta \), so the weakest (true) lower bound on expansion occurs where the two are equal:

\[ 3\beta \alpha n + (1-\beta )\alpha n = \Bigl(1+\tfrac {c-1}{2d}\Bigr)(1-\beta )\alpha n \ \Longrightarrow \beta = \frac{\frac{c-1}{2d}}{3+\frac{c-1}{2d}}. \]

Substituting this \(\beta \) back, the set of \(\alpha n\) variables has at least

\[ \alpha n\! \left(1 + \frac{2\, \frac{c-1}{2d}}{3+\frac{c-1}{2d}}\right) \]

neighbours, as claimed.