10.6 Notes on Chapter 9

Section 10.1.1. Modern interest in expanders and their algorithmic uses goes back to the early 1980s, e.g. their use in parallel sorting networks by Ajtai et al [3], and was increased by Alon’s [29] graph-theoretic formulation of Cheeger’s inequality. The conference proceedings [157] provides an overview.

Edge-expansion, measured by parameters like $h$ at (10.2), is more relevant to random walk than vertex-expansion. Walters [334] compares definitions. What we call “expander” is often called bounded-degree expander.

Section 10.1.2. Ajtai et al [4], studying the “amplification of randomness” problems in section 10.4.1, was perhaps the first explicit use of random walk on expanders. In Theorem 10.1, the upper bounds on $\tau^{*}$ and $EC$ go back to Chandra et al [85].

Section 10.1.3. With the failure of conjecture (10.9), the next natural conjecture is: on a $r$-regular graph

It’s not clear whether such conjectures are worth pursuing.

Section 10.2. More classical accounts of spectral graph theory are in Cvetkovic et al [107, 106].

On a not-necessarily-regular graph, Chung [95] studies the eigenvalues of the matrix ${\cal L}$ defined by

In the regular case, $-{\cal L}$ is the $Q$-matrix of transition rates for the continuous-time random walk, and so Chung’s eigenvalues are identical to our continuous-time eigenvalues. In the non-regular case there is no simple probabilistic interpretation of ${\cal L}$ and hence no simple probabilistic interpretation of results involving the relaxation time $1/\lambda_{2}$ associated with ${\cal L}$.

Section 10.2.1. Chung [95] Chapter 3 gives more detailed results about diameter and eigenvalues. One can slightly sharpen the argument for Proposition 10.4 by using (10.11) and the analog of Chapter 4 Lemma 26 (yyy 10/11/94 version) in which the threshold for $\tau_{1}^{{\rm disc}}$ is set at $1-\varepsilon$. Such arguments give bounds closer to that of [95] Corollary 3.2: if $G$ is not complete then

Section 10.2.2. Chung [95] section 4.4 analyzes a somewhat related routing problem. Broder et al [68] analyze a dynamic version of path selection in expanders.

Section 10.3.1. Example 10.7 (union of sets) and the more general DNF counting problem were studied systematically by Karp et al [210]; see also [265] section 11.2.

The Solovay-Strassen test of primality depends on a certain property of the Jacobi symbol: see [265] section 14.6 for a proof of this property.

Section 10.4.1. Several other uses of random walks on expanders can be found in Ajtai et al [4], Cohen and Wigderson [97], Impagliazzo and Zuckerman [188].

Section 10.4.4. Tetali [327] discussions extensions of parts (a,b) of Proposition 10.10 to nonsymmetric cost matrices.

Section 10.5. More extensive treatments of approximate counting are in Sinclair [308] and Motwani and Raghavan [265] Chapter 12.

Jerrum et al [200] formalize a notion of self-reducibility and show that, under this condition, approximate counting can be performed in polynomial time iff approximately uniform sampling can. See Sinclair [308] section 1.4 for a nice exposition.

Abstractly, we are studying randomized algorithms which produce a random estimate $\hat{a}(d)$ of a numerical quantity $a(d)$ (where $d$ measures the “size” of the problem) together with a rigorous bound of the form

Such a scheme is a FPRAS (fully polynomial randomized approximation scheme) if the cost of the algorithm is bounded by a polynomial in $d$, $1/\varepsilon$ and $\log 1/\delta$. Here the conclusion involving $\log 1/\delta$ is what emerges from proofs using large deviation techniques.

Section 10.5.1. Other papers on the volume problem and the related problem of sampling from a log-concave distribution are Lovász and Simonovits [238], Applegate and Kannan [33], Dyer and Frieze [136], Lovász and Simonovits [239] and Frieze et al [158].

Section 10.5.2. In the background is the problem of approximating the permanent

of a $n\times n$ non-negative matrix, where the sum is over all permutations $\sigma$. When $A$ is the adjacency matrix of a $n\ +\ n$ bipartite graph, per(A) is the number of perfect matchings. Approximate counting of perfect matchings is in principle similar to approximate counting of all matchings; one seeks to use the chain in section 10.5.2 restricted to ${\cal M}_{i}\cup{\cal M}_{i-1}$, where ${\cal M}_{i}$ is the set of matchings with exactly $i$ edges. But successful analysis of this chain requires that we have a dense graph, with minimum degree $>n/2$. Jerrum and Sinclair [196] gave the first analysis, using the Cheeger inequality and estimating expansion via distinguished paths. Sinclair [308] Chapter 3 and Motwani and Raghavan [265] Chapter 11 give more detailed expositions. Subsequently it was realized that using the distinguished paths technique directly to bound $\tau_{2}$ was more efficient. A more general setting is to seek to sample from the non-uniform distribution on matchings $M$

for a parameter $\lambda>1$. The distinguished paths technique [197, 199] giving (10.22) works in this setting to give