7 Symmetric Graphs and Chains (January 31, 1994)

7.2 Arc-transitivity

Example 7.14 shows that random walk on a Cayley graph does not necessarily have the property that EvTwE_{v}T_{w} is the same for all edges (v,w)(v,w). It is natural to consider some stronger symmetry condition which does imply this property. Call a graph arc-transitive if for each 44-tuple of vertices (v1,w1,v2,w2)(v_{1},w_{1},v_{2},w_{2}) such that (v1,w1)(v_{1},w_{1}) and (v2,w2)(v_{2},w_{2}) are edges, there exists an automorphism γ\gamma such that γ(v1)=w1,γ(v2)=w2\gamma(v_{1})=w_{1},\gamma(v_{2})=w_{2}. Arc-transitivity is stronger than vertex-transitivity, and immediately implies that EvTwE_{v}T_{w} is constant over edges (v,w)(v,w).

Lemma 7.19

On a nn-vertex arc-transitive graph,

(i) EvTw=n-1E_{v}T_{w}=n-1 for each edge (v,w)(v,w).

(ii) EvTwn-2+d(v,w)E_{v}T_{w}\geq n-2+d(v,w) for all wvw\neq v.

Proof. (i) follows from EvTv+=nE_{v}T^{+}_{v}=n. For (ii), write N(w)N(w) for the set of neighbors of ww. Then


and TN(w)d(v,N(w))=d(v,w)-1T_{N(w)}\geq d(v,N(w))=d(v,w)-1.

In particular, minwvEvTw=n-1\min_{w\neq v}E_{v}T_{w}=n-1, which gives the following bounds on mean cover time ECEC. The first assertion uses Matthews method for expectations (Chapter 2 yyy) and the second follows from Theorem 7.9.

Corollary 7.20

On a nn-vertex arc-transitive graph, EC(n-1)hn-1EC\geq(n-1)h_{n-1}. And if τ0/n1\tau_{0}/n\rightarrow 1 and τ2=o(n/logn)\tau_{2}=o(n/\log n) then

C-τ0lognτ0dη\frac{C-\tau_{0}\log n}{\tau_{0}}\ \stackrel{d}{\rightarrow}\ \eta (7.26)

Note that the lower bound (n-1)hn-1(n-1)h_{n-1} is attained on the complete graph. It is not known whether this exact lower bound remains true for vertex-transitive graphs, but this would be a consequence of Chapter 6 Open Problem yyy. Note also that by xxx the hypothesis τ0/n1\tau_{0}/n\rightarrow 1 can only hold if the degrees tend to infinity.

Corollary 7.20 provides easily-checkable conditions for the distributional limit for cover times, in examples with ample symmetry, such as the card-shuffling examples in the next section. Note that

(7.26) and τ0=n(1+b+o(1)logn) imply C-nlogn-bnndη.(\ref{Cext8})\mbox{ and }\tau_{0}=n\left(1+\frac{b+o(1)}{\log n}\right)\mbox{ % imply }\frac{C-n\log n-bn}{n}\ \stackrel{d}{\rightarrow}\ \eta.

Thus on the dd-cube (Chapter 5 yyy) τ0=n(1+1+o(1)d)=n(1+log2+o(1)logn)\tau_{0}=n\left(1+\frac{1+o(1)}{d}\right)=n\left(1+\frac{\log 2+o(1)}{\log n}\right) and so

C-nlogn-nlog2ndη.\frac{C-n\log n-n\log 2}{n}\ \stackrel{d}{\rightarrow}\ \eta.

7.2.1 Card-shuffling examples

These examples are formally random flights on the permutation group, though we shall describe them informally as models for random shuffles of a mm-card deck. Write XtX_{t} for the configuration of the deck after tt shuffles, and write Yt=f1(Xt)Y_{t}=f_{1}(X_{t}) for the position of card 11 after tt shuffles. In most examples (and all those we discuss) YtY_{t} is itself a Markov chain on {1,2,,m}\{1,2,\ldots,m\}. Example 7.21, mentioned in Chapter 1 xxx, has become the prototype for use of group representation methods.

Example 7.21

Card-shuffling via random transpositions.

The model is

Make two independent uniform choices of cards, and interchange the positions of the two cards.

With chance 1/m1/m the same card is chosen twice, so the “interchange” has no effect. This model was studied by Diaconis and Shahshahani [120], and more concisely in the book Diaconis [123] Chapter 3D. The chain YtY_{t} has transition probabilities

ij\displaystyle i\rightarrow j probability 2/m2,  ji\displaystyle 2/m^{2},\ j\neq i
ii\displaystyle i\rightarrow i probability 1-2(m-1)m2\displaystyle 1-\frac{2(m-1)}{m^{2}}

This is essentially random walk on the complete mm-graph (precisely: the continuized chains are deterministic time-changes of each other) and it is easy to deduce that (Yt)(Y_{t}) has relaxation time m/2m/2. So by the contraction principle xxx the card-shuffling process has τ2m/2\tau_{2}\geq m/2, and group representation methods show

τ2=m/2.\tau_{2}=m/2. (7.27)

Since the chance of being in the initial state after 11 step is 1/m1/m and after 22 steps in O(1/m2)O(1/m^{2}), the local transience heuristic (7.10) suggests

τ0=m!(1+1/m+O(1/m2))\tau_{0}=m!(1+1/m+O(1/m^{2})) (7.28)

which can be verified by group representation methods (see Flatto et al [152]). The general bound on τ1\tau_{1} in terms of τ2\tau_{2} gives only τ1=O(τ2logm!)=O(m2logm)\tau_{1}=O(\tau_{2}\log m!)=O(m^{2}\log m). In fact group group representation methods ([123]) show

 there is a variation cutoff at 12mlogm.\mbox{ there is a variation cutoff at }\frac{1}{2}m\log m. (7.29)
Example 7.22

Card-shuffling via random adjacent transpositions.

The model is

With probability 1/(m+1)1/(m+1) do nothing. Otherwise, choose one pair of adjacent cards (counting the top and bottom cards as adjacent), with probability 1/(m+1)1/(m+1) for each pair, and interchange them.

The chain YtY_{t} has transition probabilities

i\displaystyle i\rightarrow i+1\displaystyle i+1 probability 1/(m+1)\displaystyle\mbox{ probability }1/(m+1)
i\displaystyle i\rightarrow i-1\displaystyle i-1 probability 1/(m+1)\displaystyle\mbox{ probability }1/(m+1)
i\displaystyle i\rightarrow i\displaystyle i probability (m-1)/(m+1)\displaystyle\mbox{ probability }(m-1)/(m+1)

with i±1i\pm 1 counted modulo mm. This chain is (in continuous time) just a time-change of random walk on the mm-cycle, so has relaxation time


So by the contraction principle xxx the card-shuffling process has τ2a(m)\tau_{2}\geq a(m), and (xxx unpublished Diaconis work) in fact

τ2=a(m)m3/4π2.\tau_{2}=a(m)\sim m^{3}/4\pi^{2}.

A coupling argument which we shall present in Chapter xxx gives an upper bound τ1=O(m3logm)\tau_{1}=O(m^{3}\log m) and (xxx unpublished Diaconis work) in fact

τ1=Θ(m3logm).\tau_{1}=\Theta(m^{3}\log m).

The local transience heuristic (7.10) again suggests


but this has not been studied rigorously.

Many variants of these examples have been studied, and we will mention a generalization of Examples 7.21 and 7.22 in Chapter xxx. Here is another example, from Diaconis and Saloff-Coste [115], which illustrates the use of comparison arguments.

Example 7.23

A slow card-shuffling scheme.

The model is: with probability 1/31/3 each, either

(i) interchange the top two cards

(ii) move the top card to the bottom

(iii) move the bottom card to the top.

This process is random walk on a certain Cayley graph, which (for m3m\geq 3) is not arc-transitive. Writing dd for distances in the graph and writing

β=max(d(σ,id):σ a transposition ),\beta=\max(d(\sigma,\mbox{id}):\sigma\mbox{ a transposition }),

it is easy to check that β3m\beta\leq 3m. Comparing the present chain with the “random transpositions” chain (Example 7.21), denoted by ~\tilde{\ }, Theorem 7.16 implies

τ2τ2~3β2.\frac{\tau_{2}}{\tilde{\tau_{2}}}\leq 3\beta^{2}.

Since τ2~=m/2\tilde{\tau_{2}}=m/2 we get


7.2.2 Cover times for the dd-dimensional torus ZNdZ^{d}_{N}.

This is Example yyy from Chapter 5, with n=Ndn=N^{d} vertices, and is clearly arc-transitive. Consider asymptotics as NN\rightarrow\infty for dd fixed. We studied mean hitting times in this example in Chapter 5. Here τ0/n↛1\tau_{0}/n\not\rightarrow 1, so we cannot apply Corollary 7.20. For d=1d=1 the graph is just the dd-cycle, treated in Chapter 6 yyy. For d3d\geq 3, Chapter 5 yyy gave

E0TinRd as N,  |i|E_{0}T_{i}\sim nR_{d}\mbox{ as }N\rightarrow\infty,\ |i|\rightarrow\infty

where |i||i| is Euclidean distance on the torus, i.e.


So ECEC has the asymptotic upper bound RdnlognR_{d}n\log n. Now if we apply the subset form of Matthews method (Chapter 6 yyy) to the subset

A={(j1m,,jdm):1jiNm}A=\{(j_{1}m,\ldots,j_{d}m):1\leq j_{i}\leq\frac{N}{m}\} (7.30)

then we get a lower bound for ECEC asymptotic to

log|A|×nRd.\log|A|\times nR_{d}.

By taking m=m(n)m=m(n)\uparrow\infty slowly, this agrees with the upper bound, so we find

Corollary 7.24

On the dd-dimensional torus with d3d\geq 3,

ECRdnlogn.EC\sim R_{d}n\log n.

Perhaps surprisingly, the case d=2d=2 turns out to be the hardest of all explicit graphs for the purposes of estimating cover times. (Recall this case is the white screen problem Chapter 1 xxx.) Loosely, the difficulty is caused by the fact that τ2=Θ(nlogn)\tau_{2}=\Theta(n\log n) – recall from Chapter 6 yyy that another example with this property, the balanced tree, is also hard. Anyway, for the case d=2d=2 the calculations in Chapter 5 yyy gave

E0Tin(2πlog|i|+O(1)).E_{0}T_{i}\sim n\left(\frac{2}{\pi}\log|i|\ +O(1)\right).

This leads to the upper bound in Corollary 7.25 below. For the lower bound, we repeat the d3d\geq 3 argument using a subset of the form (7.30) with mm\rightarrow\infty, and obtain a lower bound asymptotic to

2πlogm×log(n2/m2).\frac{2}{\pi}\log m\ \times\ \log(n^{2}/m^{2}).

The optimal choice is mn1/2m\sim n^{1/2}, leading to the lower bound below.

Corollary 7.25

On the 22-dimensional torus ZN2Z^{2}_{N},

(14π-o(1))nlog2nEC(1π+o(1))nlog2n.\left(\frac{1}{4\pi}-o(1)\right)n\log^{2}n\leq EC\leq\left(\frac{1}{\pi}+o(1)% \right)n\log^{2}n.

Lawler [222] has improved the constant in the lower bound to 12π\frac{1}{2\pi} – see Notes. It is widely believed that the upper bound is in fact the limit.

Open Problem 7.26

Prove that, on the 22-dimensional torus ZN2Z^{2}_{N},

EC1πnlog2n.EC\sim\frac{1}{\pi}\ n\log^{2}n.

The usual distributional limit

C-τ0lognτ0dη\frac{C-\tau_{0}\log n}{\tau_{0}}\ \stackrel{d}{\rightarrow}\ \eta

certainly fails in d=1d=1 (see Chapter 6 yyy). It has not been studied in d2d\geq 2, but the natural conjecture it that it is true for d3d\geq 3 but false in d=2d=2. Note that (by Chapter 6 yyy) the weaker concentration result

C/ECd 1C/EC\ \stackrel{d}{\rightarrow}\ 1

holds for all d2d\geq 2.

7.2.3 Bounds for the parameters

In Chapter 6 we discussed upper bounds on parameters τ\tau for regular graphs. One can’t essentially improve these bounds by imposing symmetry conditions, because the bounds are attained (up to constants) by the nn-cycles. But what if we exclude the nn-cycles? Example 7.14 shows that one can invent vertex-transitive graphs which mimic the nn-cycle, but it is not clear whether such arc-transitive graphs exist. So perhaps the next-worst arc-transitive graph is Zm2Z_{m}^{2}.

Open Problem 7.27

Is it true that, over arc-transitive graphs excluding the nn-cycles, τ*=O(nlogn)\tau^{*}=O(n\log n), τ2=O(n)\tau_{2}=O(n) and τ*2τ0=1+o(1)\frac{\tau^{*}}{2\tau_{0}}=1+o(1)?

7.2.4 Group-theory set-up

Recall that the Cayley graph associated with a set 𝒢{\cal G} of generators of a group II has edges

{(v,vg);vI,g𝒢}\{(v,vg);v\in I,g\in\mbox{${\cal G}$}\}

where we assume 𝒢{\cal G} satisfies

(i) g𝒢g\in\mbox{${\cal G}$} implies g-1𝒢g^{-1}\in\mbox{${\cal G}$}.

To ensure that the graph is arc-transitive, it is sufficient to add the condition

(ii) for each pair g1,g2g_{1},g_{2} in 𝒢{\cal G}, there exists a group automorphism γ\gamma such that γ(id)=id\gamma({\rm id})={\rm id} and γ(g1)=g2\gamma(g_{1})=g_{2}.

In words, “the stabilizer acts transitively on 𝒢{\cal G}”. This is essentially the general case: see [71] Prop. A.3.1.

As a related concept, recall that elements x,yx,y of a group II are conjugate if x=g-1ygx=g^{-1}yg for some group element gg. This is an equivalence relation which therefore defines conjugacy classes. It is easy to check that a conjugacy class must satisfy condition (ii). Given a conjugacy class CC one can consider the uniform distribution μC\mu_{C} on CC and then consider the random flight with step distribution μC\mu_{C}. Such random flights fit into the framework of section 7.2, and Example 7.21 and the torus ZNdZ^{d}_{N} are of this form. On the other hand, Example 7.22 satisfies (i) and (ii) but are not random flights with steps uniform on a conjugacy class.