  We study the trajectory of a simple random walk on a d-regular graph with d>2
and locally tree-like structure as the number n of vertices grows. Examples of
such graphs include random d-regular graphs and large girth expanders. For
these graphs, we investigate percolative properties of the set of vertices not
visited by the walk until time un, where u>0 is a fixed positive parameter. We
show that this so-called vacant set exhibits a phase transition in u in the
following sense: there exists an explicitly computable threshold u* such that,
with high probability as n grows, if u<u*, then the largest component of the
vacant set has a volume of order n, and if u>u*, then it has a volume of order
log(n). The critical value u* coincides with the critical intensity of a random
interlacement process (introduced by Sznitman [arXiv:0704.2560]) on a d-regular
tree. We also show that the random interlacement model describes the structure
of the vacant set in local neighbourhoods.
