Giant vacant component left by a random walk in a random \(d\)-regular graph (Q1944664)

The trajectory is considered of a simple random walk on a regular graph of order \(n\) with tree-like structure for increasing \(n\). The vacant set is the complement of the trajectory. Its percolative properties as \(n\) increases are investigated at time \(un\) where \(u\) is a fixed positive parameter. It is shown that there exists a threshold for \(u\) such that the largest component of the vacant set is of order \(n\) below the threshold and of order \(\log(n)\) above the threshold. Connections with the random interlacement model are also given.