# 7.2 Arc-transitivity

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

###### Lemma 7.19

On a $n$-vertex arc-transitive graph,

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

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

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

 $E_{v}T_{w}=E_{v}T_{N(w)}+(n-1)$

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

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

###### Corollary 7.20

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

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

Note that the lower bound $(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 $\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

 $(\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 $d$-cube (Chapter 5 yyy) $\tau_{0}=n\left(1+\frac{1+o(1)}{d}\right)=n\left(1+\frac{\log 2+o(1)}{\log n}\right)$ and so

 $\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 $m$-card deck. Write $X_{t}$ for the configuration of the deck after $t$ shuffles, and write $Y_{t}=f_{1}(X_{t})$ for the position of card $1$ after $t$ shuffles. In most examples (and all those we discuss) $Y_{t}$ is itself a Markov chain on $\{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/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 $Y_{t}$ has transition probabilities

 $\displaystyle i\rightarrow j$ probability $\displaystyle 2/m^{2},\ j\neq i$ $\displaystyle i\rightarrow i$ probability $\displaystyle 1-\frac{2(m-1)}{m^{2}}$

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

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

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

 $\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 $\tau_{1}$ in terms of $\tau_{2}$ gives only $\tau_{1}=O(\tau_{2}\log m!)=O(m^{2}\log m)$. In fact group group representation methods ([123]) show

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

The model is

With probability $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)$ for each pair, and interchange them.

The chain $Y_{t}$ has transition probabilities

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

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

 $a(m)\equiv\frac{m+1}{2}\frac{1}{1-\cos(2\pi/m)}\sim\frac{m^{3}}{4\pi^{2}}.$

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

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

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

 $\tau_{1}=\Theta(m^{3}\log m).$

The local transience heuristic (7.10) again suggests

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

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/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 $m\geq 3$) is not arc-transitive. Writing $d$ for distances in the graph and writing

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

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

 $\frac{\tau_{2}}{\tilde{\tau_{2}}}\leq 3\beta^{2}.$

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

 $\tau_{2}\leq\frac{27m^{3}}{2}.$

## 7.2.2 Cover times for the $d$-dimensional torus $Z^{d}_{N}$.

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

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

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

 $|(i_{1},\ldots,i_{d})|^{2}=\sum_{u=1}^{d}(\min(i_{u},N-i_{u}))^{2}.$

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

 $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 $EC$ asymptotic to

 $\log|A|\times nR_{d}.$

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

###### Corollary 7.24

On the $d$-dimensional torus with $d\geq 3$,

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

Perhaps surprisingly, the case $d=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 $\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=2$ the calculations in Chapter 5 yyy gave

 $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 $d\geq 3$ argument using a subset of the form (7.30) with $m\rightarrow\infty$, and obtain a lower bound asymptotic to

 $\frac{2}{\pi}\log m\ \times\ \log(n^{2}/m^{2}).$

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

###### Corollary 7.25

On the $2$-dimensional torus $Z^{2}_{N}$,

 $\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 $\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 $2$-dimensional torus $Z^{2}_{N}$,

 $EC\sim\frac{1}{\pi}\ n\log^{2}n.$

The usual distributional limit

 $\frac{C-\tau_{0}\log n}{\tau_{0}}\ \stackrel{d}{\rightarrow}\ \eta$

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

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

holds for all $d\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 $n$-cycles. But what if we exclude the $n$-cycles? Example 7.14 shows that one can invent vertex-transitive graphs which mimic the $n$-cycle, but it is not clear whether such arc-transitive graphs exist. So perhaps the next-worst arc-transitive graph is $Z_{m}^{2}$.

###### Open Problem 7.27

Is it true that, over arc-transitive graphs excluding the $n$-cycles, $\tau^{*}=O(n\log n)$, $\tau_{2}=O(n)$ and $\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 $I$ has edges

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

where we assume ${\cal G}$ satisfies

(i) $g\in\mbox{{\cal G}}$ implies $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 $g_{1},g_{2}$ in ${\cal G}$, there exists a group automorphism $\gamma$ such that $\gamma({\rm id})={\rm id}$ and $\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,y$ of a group $I$ are conjugate if $x=g^{-1}yg$ for some group element $g$. 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 $C$ one can consider the uniform distribution $\mu_{C}$ on $C$ and then consider the random flight with step distribution $\mu_{C}$. Such random flights fit into the framework of section 7.2, and Example 7.21 and the torus $Z^{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.