GIANT VACANT COMPONENT LEFT BY A RANDOM WALK IN A RANDOM d-REGULAR GRAPH
GIANT VACANT COMPONENT LEFT BY A RANDOM WALK IN A RANDOM d-REGULAR GRAPH
复制标题
随机 d-正则图中随机游走留下的巨大空余分量
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
David Windisch
中科院分区：
文献类型：
--
作者：
J. Černý;A. Teixeira;David Windisch
我们研究了D-3的简单随机步行的轨迹，随着顶点的数量n的数量n，这些图的数量n包括随机的Dregular图图，我们调查了步行访问的一组顶点的渗透特性，直到u> 0是固定的正参数，我们表明，这种所谓的空置集在以下意义上在u中表现出一个相变：存在明确的可计算阈值u吗？ D-regular树上的讲述过程还表明，随机插条模型描述了当地社区中空置的结构。
We study the trajectory of a simple random walk on a d-regular graph with d � 3 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? 2 (0,1 ) such that, with high probability as n grows, if u u?, then it has a volume of order logn. The critical value u? coincides with the critical intensity of a random interlacement process on a d-regular tree. We also show that the random interlacements model describes the structure of the vacant set in local neighbourhoods.