Critical window for the vacant set left by random walk on random regular graphs1. Issue 3 (12th May 2012)

• Record Type: Journal Article
• Authors: Černý, Jiří; Teixeira, Augusto
• Is Part Of: Random structures & algorithms. Volume 43:Issue 3(2013)
• Page Start: 313
• Page End: 337
• Publication Date: 2012-05-12
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20425
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>We consider the simple random walk on a random <italic>d</italic> ‐regular graph with <italic>n</italic> vertices, and investigate percolative properties of the set of vertices not visited by the walk until time <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\left\lfloor un \right\rfloor\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg2pr8ddt6" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />, where <italic>u</italic> &gt; 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 <italic>u</italic> = <italic>u</italic>_⋆: there is a giant component if <italic>u</italic> &lt; <italic>u</italic>_⋆ and only small components when <italic>u</italic> &gt; <italic>u</italic>_⋆. In this paper we show the existence of a critical window of size <italic>n</italic>^‐1/3 around <italic>u</italic>_⋆. In this window the size of the largest cluster is of order <italic>n</italic>^2/3. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013</p> </abstract>