Combinatorics Seminar

When: Sunday, January 17, 10am Where: Schreiber 309 Speaker: David Windisch, Weizmann Institute Title: Phase transition for the vacant set of a random walk on a random regular graph

Abstract:

We consider 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 the sizes of components of the random graph obtained by removing all vertices visited by the random walk in [un] steps, where u > 0 is a fixed parameter. We show that there exists an explicitly computable threshold 0 < u_* < \infty such that for large n, there is typically exactly one such component of volume O(n) if u < u_*, whereas all components are smaller than O(log n) if u > u_*. The critical value u_* coincides with the critical intensity of a random interlacement on a d-regular tree.

Joint work with Jiri Cerny and Augusto Teixeira.