Questions: Expander Graphs

Question 1

A d-regular graph on n vertices has eigenvalues d = lambda_1 >= lambda_2 >= ... >= lambda_n. The graph is a good expander when the spectral gap d - |lambda_2| is large. What does the spectral gap control?

• A. The number of edges in the graph
• B. The mixing time of random walks (how quickly the walk distribution converges to uniform) and the edge expansion (minimum ratio of boundary edges to subset size) — larger spectral gap means faster mixing and better expansion
• C. The chromatic number of the graph
• D. The diameter of the graph only, not expansion

Answer: (B)

The expander mixing lemma quantifies: for any two vertex sets S, T, the number of edges between them deviates from the 'expected' d|S||T|/n by at most lambda_2 * sqrt(|S||T|). When lambda_2 is small relative to d, edge distribution is near-uniform. The Cheeger inequality connects the spectral gap to edge expansion h: (d - lambda_2)/2 <= h <= sqrt(2d(d - lambda_2)). For random walks, the distribution after t steps deviates from uniform by at most n * (lambda_2/d)^t in total variation, so mixing time is O(d/(d - lambda_2) * log n). All three properties — edge distribution, expansion, and mixing — are controlled by the spectral gap.

Question 2

Explicit constructions of Ramanujan graphs achieve the optimal spectral gap: |lambda_2| <= 2*sqrt(d-1) for d-regular graphs. The Alon-Boppana bound proves this is the best possible for any infinite family.

• T. True
• F. False

Answer: True

The Alon-Boppana theorem states that for any infinite family of d-regular graphs, lim inf |lambda_2| >= 2*sqrt(d-1). Ramanujan graphs achieve this bound with equality — they have the smallest possible |lambda_2| for their degree, making them optimal expanders. Lubotzky-Phillips-Sarnak (1988) and Margulis (1988) gave the first explicit constructions for d = p+1 (prime p) using deep results from number theory (the Ramanujan conjecture for automorphic forms). Marcus, Spielman, and Srivastava (2015) proved that bipartite Ramanujan graphs exist for all degrees, winning the Pólya Prize.

Question 3

Explain how expander graphs are used for derandomization — specifically, how a random walk on an expander can replace independent random samples.

Model answer: Suppose an algorithm needs k independent random samples from {1,...,n}, each requiring log(n) random bits, for k*log(n) total random bits. Instead, pick one random vertex on a d-regular expander on n vertices (log n bits), then take a random walk of length k-1 (each step requires log d bits), using each visited vertex as a sample. Total random bits: log n + (k-1) * log d, which is much less than k * log n. The expander mixing lemma ensures that the walk visits vertices in approximately the correct frequencies — the spectral gap bounds the deviation from independence. For algorithms whose analysis only requires bounded pairwise (or limited) dependence, expander walks provide sufficient pseudorandomness at dramatically reduced random-bit cost.

This is one of the key derandomization techniques: replacing true randomness with pseudorandomness generated by deterministic walks on structured graphs. The Ajtai-Komlós-Szemerédi sorting network and the RL = L conjecture both connect to expander-based derandomization. The general principle is that expanders 'spread out' probability mass so efficiently that walks on them approximate independent sampling.

Question 4

Every random d-regular graph is a good expander with high probability for d >= 3.

• T. True
• F. False

Answer: True

A random d-regular graph on n vertices has |lambda_2| <= 2*sqrt(d-1) + epsilon with high probability for any fixed epsilon > 0, essentially achieving the Ramanujan bound. This is a consequence of Friedman's theorem (2003, proved the Alon conjecture): a random d-regular graph is 'nearly Ramanujan.' The probabilistic method thus shows that good expanders are abundant, even though explicit constructions require sophisticated algebraic machinery. This situation — random objects have good properties, but explicit constructions are hard — is a recurring theme in combinatorics and theoretical computer science.