A note on the vacant set of random walks on the hypercube and other regular graphs of high degree

Abstract

We consider a random walk on a $d$-regular graph $G$ where $d\to \infty$ and $G$ satisfies certain conditions. Our prime example is the $d$-dimensional hypercube, which has $n=2^d$ vertices. We explore the likely component structure of the vacant set, i.e. the set of unvisited vertices. Let $\Lambda (t)$ be the subgraph induced by the vacant set of the walk at step $t$. We show that if certain conditions are satisfied then the graph $\Lambda (t)$ undergoes a phase transition at around $t^{\ast }=n{\log }_{e}d$. Our results are that if $t\le (1-\epsilon )t^{\ast }$ then w.h.p. as the number vertices $n\to \infty$, the size $L_1(t)$ of the largest component satisfies $L_1\gg \log n$ whereas if $t\geq(1+\e)t^*$ then $L_1(t)=o(\log n)$.