10 Some Graph Theory and Randomized Algorithms (September 1 1999)

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 hh 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 ECEC 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 rr-regular graph

τ0=?O(max(n,τ2)max(logn,r)).\tau_{0}=^{?}O(\max(n,\tau_{2})\max(\log n,r)).

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

vw\displaystyle{\cal L}_{vw} =\displaystyle= 1, w=v\displaystyle 1,\quad w=v (10.23)
=\displaystyle= -(dvdw)-1/2 for an edge (v,w)\displaystyle-(d_{v}d_{w})^{-1/2}\mbox{ for an edge }(v,w)
=\displaystyle= 0 else.\displaystyle 0\mbox{ else}.

In the regular case, --{\cal L} is the QQ-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/λ21/\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 τ1disc\tau_{1}^{{\rm disc}} is set at 1-ε1-\varepsilon. Such arguments give bounds closer to that of [95] Corollary 3.2: if GG is not complete then

Δlog(n-1)log3-λ21+λ2.\Delta\leq\left\lceil\frac{\log(n-1)}{\log{\textstyle\frac{3-\lambda_{2}}{1+% \lambda_{2}}}}\right\rceil.

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 a^(d)\hat{a}(d) of a numerical quantity a(d)a(d) (where dd measures the “size” of the problem) together with a rigorous bound of the form

P((1-ε)a(d)a^(d)(1+ε)a(d))1-δ.P((1-\varepsilon)a(d)\leq\hat{a}(d)\leq(1+\varepsilon)a(d))\geq 1-\delta.

Such a scheme is a FPRAS (fully polynomial randomized approximation scheme) if the cost of the algorithm is bounded by a polynomial in dd, 1/ε1/\varepsilon and log1/δ\log 1/\delta. Here the conclusion involving log1/δ\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

perA:=σi=1nAiσ(i){\rm per}A:=\sum_{\sigma}\prod_{i=1}^{n}A_{i\sigma(i)}

of a n×nn\times n non-negative matrix, where the sum is over all permutations σ\sigma. When AA is the adjacency matrix of a n+nn\ +\ 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 ii-1{\cal M}_{i}\cup{\cal M}_{i-1}, where i{\cal M}_{i} is the set of matchings with exactly ii edges. But successful analysis of this chain requires that we have a dense graph, with minimum degree >n/2>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 τ2\tau_{2} was more efficient. A more general setting is to seek to sample from the non-uniform distribution on matchings MM


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