1
$\begingroup$

For many planar graphs of bounded degree (binary tree, lattice, cycle) the (1/4)-mixing time and the cover time are equal, up to log-factors. Is this always the case?

$\endgroup$
1
$\begingroup$

The answer turns out to be no. A counterexample, kindly suggested to me by Balász Gerencsér, is a $\sqrt{N}$ by $\sqrt{N}$ grid, with a path of length $\sqrt{N}$ glued to it. One can show that

  • the mixing time of a simple random walk on this graph is $O(N\log N)$ (by combining Cheeger's inequality and the Spielman-Teng [1] bound on the spectral gap)
  • the cover time of a simple random walk on this graph is $\Omega(N^{3/2})$ (by combining Matthews method with an expression of the hitting time using effective resistance)

[1] Spielman, Daniel A., and Shang-Hua Teng. "Spectral partitioning works: Planar graphs and finite element meshes." Linear Algebra and its Applications 421.2-3 (2007): 284-305.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.