A Note on the Vacant Set of Random Walks on the Hypercube and Other Regular Graphs of High Degree

We consider a random walk on a d-regular graph G where d → ∞ and G satisfies certain conditions. Our prime example is the d-dimensional hypercube, which has n = 2d vertices. We explore the likely component structure of the vacant set, i.e. the set of unvisited vertices. Let Λ(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 Λ(t) undergoes a phase transition at around t* = n loge d. Our results are that if t ≤ (1 − ε)t* then w.h.p. as the number vertices n → ∞, the size L1(t) of the largest component satisfies ≫ n whereas if t ≥ (1 + ε)t* then L1(t) = o(log n).