STOC'91 paper on local expansion of vertex-transitive graphs, escape of a random walk from a corner, and sampling a group

• L. Babai: Local expansion of vertex-transitive graphs and random generation in finite groups. Proc. 23rd ACM STOC, 1991, 164--167.

This paper shows that vertex-transitive graphs locally expand at least at the rate of a cycle, studies the escape time from small-diameter subsets, and proves that one can sample groups nearly uniformly in polynomial time.

The version of the STOC'91 paper posted here is a slight update of the STOC version (written shortly after the STOC'91 meeting); the only essential change is that a full proof of a local variant of Alon's Cheeger-type inequality (Lemma 4.1) stated in the STOC version has been added.

The Local Expansion Theorem applies to all locally finite graphs with a vertex-transitive group action with finite stabilizers. This includes all finite vertex-transitive graphs, the Cayley graphs of all finitely generated groups, and certain other infinite vertex-transitive graphs.

A more elegant proof of the Local Expansion Theorem was subsequently given in

• L. Babai and M. Szegedy: Local Expansion of Symmetrical Graphs. Combinatorics, Probability, and Computing 1 (1992), 1-11.

This version improves the constant by roughly a factor of 2, and, more significantly, it extends the result to all infinite locally finite unimodular vertex-transitive graphs. (This is not explicitly stated but is implicit in the proof which is in essence a mass transport counting argument.)

Comments on the escape time of random walks. Let U be a finite subset of the vertices of a (finite or infinite) d-regular graph X. Let us consider the simple random walk on X starting from a given node (the "origin"). Proposition 4.2 links the time of first exit from U to the gap d-λ where λ is the largest eigenvalue of the subgraph induced on U.

Lemma 4.1 (local version of Alon's Cheeger-type inequality) connects this gap to the minimum of the expansion rates (within the ambient graph X) of all subsets of U.

Corollary 4.3 connects these two results and implies in particular that after t steps in an expander we are likely to have reached distance Ω(t/d) from the origin. (No symmetry assumption is made in these three results.)

Theorem 5.2 draws the conclusions on vertex-transitive graphs, establishing that in a d-regular vertex-transitive graph, after t steps, the simple random walk is likely to have spent a positive fraction of its time at distance at least Ω(t/d)^1/3 from the origin as long as this quantity does not exceed a constant fraction of the diameter of the graph. It is easy to derive from this result that the expected distance also satisfies this inequality.

The result applies to all finite vertex-transitive graphs and all infinite locally finite unimodular vertex-transitive graphs. The case of finite vertex-transitive graphs and infinite locally finite vertex-transitive graphs with finite stabilizers is covered in the paper; the extension to the infinite unimodular case requires the improved Local Expansion Theorem from the joint paper with Szegedy (above).