Critical window for the vacant set left by random walk on random regular graphs1. Issue 3 (12th May 2012) - Černý, Jiří; Teixeira, Augusto
Abstract We consider the simple random walk on a random d ‐regular graph with n vertices, and investigate percolative properties of the set of vertices not visited by the walk until time <![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\left\lfloor un \right\rfloor\end{align*} \end{document}]]> <inline-graphic xlink:href="ark:/27927/pgg2pr8ddt6" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, where u > 0 is a fixed positive parameter. It was shown in Černý et al., (Ann Inst Henri Poincaré Probab Stat 47 (2011) 929–968) that this so‐called vacant set exhibits a phase transition at u = u⋆: there is a giant component if u < u⋆ and only small components when u > u⋆. In this paper we show the existence of a critical window of size n‐1/3 around u⋆. In this window the size of the largest cluster is of order n2/3. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013