Vacant set of random walk on (random) graphs

Stochastic Analysis Seminar Series

The vacant set is the set of vertices not visited by a random walk on a graph G before a given time T. In the talk, I will discuss properties of this random subset of the graph, the phase transition conjectured in its connectivity properties (in the `thermodynamic limit' when the graph grows), and the relation of the problem to the random interlacement percolation.  I will then concentrate on the case when G is a large-girth expander or a random regular graph, where the conjectured phase transition (and much more) can be proved.


Jiri Cerny (ETH, Zurich)

Monday, October 10, 2011 - 15:45
to 16:45