The results so far in this chapter may be misleading in that upper bounds accommodating extremal graphs are rather uninformative for “typical” graphs. For a family of $n$-vertex graphs with $n\rightarrow\infty$, consider the property

$\tau^{*}=O(n).$ | (6.28) |

(in this order-of-magnitude discussion, $\tau^{*}$ is equivalent to $\max_{v,x}E_{v}T_{x}$). Recalling from Chapter 3 yyy that $\tau^{*}\geq 2(n-1)$, we see that (6.28) is equivalent to $\tau^{*}=\Theta(n)$. By Matthews’ method (repeated as Theorem 2.6 below), (6.28) implies $EC=O(n\log n)$, and then by Theorem 6.31 we have $EC=\Theta(n\log n)$. Thus understanding when (6.28) holds is fundamental to understanding order-of-magnitude questions about cover times. But surprisingly, this question has not been studied very carefully. An instructive example in the $d$-dimensional torus (Chapter 5 Example yyy), where (6.28) holds iff $d\geq 3$. This example, and other examples of vertex-transitive graphs satisfying (6.28) discussed in Chapter 8, suggest that (6.28) is frequently true. More concretely, the torus example suggests that the following condition (“the isoperimetric property in $2+\varepsilon$ dimensions”) may be sufficient.

Show that for real $1/2<\gamma<1$ and $\delta>0$, there exists a constant $K_{\gamma,\delta}$ with the following property. Let $G$ be a regular $n$-vertex graph such that, for any subset $A$ of vertices with $|A|\leq n/2$, there exist at least $\delta|A|^{\gamma}$ edges between $A$ and $A^{c}$. Then $\tau^{*}\leq K_{\gamma,\delta}\ n$.

The $\gamma=1$ case is implicit in results from previous chapters. Chapter 3 yyy gave the bound $\max_{i,j}E_{i}T_{j}\leq 2\max_{j}E_{\pi}T_{j}$, and Chapter 3 yyy gave the bound $E_{\pi}T_{j}\leq\tau_{2}/\pi_{j}$. This gives the first assertion below, and the second follows from Cheeger’s inequality.

On a regular graph,

$\max_{v,x}E_{v}T_{x}\leq 2n\tau_{2}\leq 16n\tau^{2}_{c}.$ |

Thus the “expander” property that $\tau_{2}=O(1)$, or equivalently that $\tau_{c}=O(1)$, is sufficient for (6.28), and the latter is the $\gamma=1$ case of Open Problem 6.20.

At the other end of the spectrum from expanders, we can consider graphs satisfying only a little more than connectivity.

xxx more details in proofs – see Fill’s comments.

Recall that a graph is $r$-edge-connected if for each proper subset $A$ of vertices there are at least $r$ edges linking $A$ with $A^{c}$. By a variant of Menger’s theorem (e.g. [86] Theorem 5.11), for each pair $(a,b)$ of vertices in such a graph, there exist $r$ paths $(a=v^{i}_{0},v^{i}_{1},v^{i}_{2},\ldots,v^{i}_{m_{i}}=b)$, $i=1,\ldots,r$ for which the edges $(v^{i}_{j},v^{i}_{j+1})$ are all distinct.

For a $r$-edge-connected graph,

$\tau^{*}\leq\frac{\bar{d}n^{2}\psi(r)}{r^{2}}$ |

where $\psi$ is defined by

$\psi\left(\frac{i(i+1)}{2}\right)=i$ |

$\psi(\cdot)\mbox{ is linear on }\left[\frac{i(i+1)}{2},\frac{(i+1)(i+2)}{2}% \right].$ |

Note $\psi(r)\sim\sqrt{2r}$. So for a $d$-regular, $d$-edge-connected graph, the bound becomes $\sim 2^{1/2}d^{-1/2}n^{2}$ for large $d$, improving on the bound from Corollary 6.9. Also, the Proposition improves on the bound implied by Chapter 4 yyy in this setting.

Proof. Given vertices $a,b$, construct a unit flow from $a$ to $b$ by putting flow $1/r$ along each of the $r$ paths $(a=v^{i}_{0},v^{i}_{1},v^{i}_{2},\ldots,v^{i}_{m_{i}}=b)$. By Chapter 3 Theorem yyy

$E_{a}T_{b}+E_{b}T_{a}\leq\bar{d}n(1/r)^{2}M$ |

where $M=\sum_{i}m_{i}$ is the total number of edges in the $r$ paths. So the issue is bounding $M$. Consider the digraph of all edges $(v^{i}_{j},v^{i}_{j+1})$. If this digraph contained a directed cycle, we could eliminate the edges on that cycle, and still create $r$ paths from $a$ to $b$ using the remaining edges. So we may assume the digraph is acyclic, which implies we can label the vertices as $a=1,2,3,\ldots,n=b$ in such a way that each edge $(j,k)$ has $k>j$. So the desired result follows from

In a digraph on vertices $\{1,2,\ldots,n\}$ consisting of $r$ paths $1=v^{i}_{0}<v^{i}_{1}<v^{i}_{2}<\ldots v^{i}_{m_{i}}=n$ and where all edges are distinct, the total number of edges is at most $n\psi(r)$.

Proof.

xxx give proof and picture.

Take vertices $\{0,1,\ldots,n-1\}$ and edges $(i,i+u\mbox{ mod }n)$ for all $i$ and all $1\leq u\leq\kappa$.

This example highlights the “slack” in Proposition 6.22. Regard $\kappa$ as large and fixed, and $n\rightarrow\infty$. Random walk on this graph is classical random walk (i.e. sums of independent steps) on the $n$-cycle, where the steps have variance $\sigma^{2}=\frac{1}{\kappa}\sum_{u=1}^{\kappa}u^{2}$, and it is easy to see

$\tau^{*}=2E_{0}T_{\lfloor n/2\rfloor}\sim\frac{(n/2)^{2}}{\sigma^{2}}=\Theta(n% ^{2}/\kappa^{2}).$ |

This is the bound Proposition 6.22 would give if the graph were $\Theta(\kappa^{2})$-edge-connected. And for a “typical” subset $A$ such as an interval of length greater than $\kappa$ there are indeed $\Omega(\kappa^{2})$ edges crossing the boundary of $A$. But by considering a singleton $A$ we see that the graph is really only $2\kappa$-edge-connected, and Proposition 6.22 gives only the weaker $O(n^{2}/\kappa^{1/2})$ bound.

xxx tie up with similar discussion of $\tau_{2}$ and connectivity being affected by small sets; better than bound using $\tau_{c}$ only.

Returning to the order-of-magnitude discussion at the start of section 6.5, let us record the simple equivalence result. Recall (cf. Chapter 4 yyy) we call parameters equivalent if their ratios are bounded by absolute constants.

The parameters $\max_{i}E_{i}C^{+}$, $E_{\pi}C^{+}$, $\min_{i}E_{i}C^{+}$, $\max_{i}E_{i}C$ and $E_{\pi}C$ are equivalent for reversible chains, but $\min_{i}E_{i}C$ is not equivalent to these.

Proof. Of the five parameters asserted to be equivalent, it is clear that $\max_{i}E_{i}C$ is the largest, and that either $\min_{i}E_{i}C^{+}$ or $E_{\pi}C$ is the smallest, so it suffices to prove

$\max_{i}E_{i}C^{+}\leq 4E_{\pi}C$ | (6.29) |

$\max_{j}E_{j}C^{+}\leq 3\min_{i}E_{i}C^{+}.$ | (6.30) |

Inequality (6.30) holds by concatenating three “cover-and-return” cycles starting at $i$ and considering the first hitting time on $j$ in the first and third cycles. In more detail, write

$\Gamma(s)=\min\{u>s:(X_{t}:s\leq t\leq u)\mbox{ covers all states}\}.$ |

For the chain started at $i$ write $C^{++}=\Gamma(C^{+})$ and $C^{+++}=\Gamma(C^{++})$. Since $T_{j}<C^{+}$ we have $\Gamma(T_{j})\leq C^{++}$. So the chain started at time $T_{j}$ has covered all states and returned to $j$ by time $C^{+++}$, implying $E_{j}C^{+}\leq EC^{+++}=3E_{i}C^{+}$. For inequality (6.29), recall the random target lemma: the mean time to hit a $\pi$-random state $V$ equals $\tau_{0}$, regardless of the initial distribution. The inequality

$E_{i}C^{+}\leq\tau_{0}+E_{\pi}C+\tau_{0}+E_{\pi}T_{i}$ |

follows from the four-step construction:

(i) Start the chain at $i$ and run until hitting a $\pi$-random vertex $V$
at time $T_{V}$;

(ii) continue until time $\Gamma(T_{V})$;

(iii) continue until hitting an independent $\pi$-random vertex $V^{\prime}$;

(iv) continue until hitting $i$.

But $E_{\pi}T_{i}\leq E_{\pi}C$, and then by the random target lemma
$\tau_{0}\leq E_{\pi}C$, so (6.29) follows.

For the final assertion, on the lollipop graph (Chapter 5 Example yyy) one has $\min_{i}E_{i}C=\Theta(n^{2})$ while the other quantities are $\Theta(n^{3})$. One can also give examples on regular graphs (see Notes).

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML