Competition with Random Walk on Random Graphs

Our goal is to understand the size and other structural properties of growth sets (indexed by time) arising from the competition with a random walk on a random graph. Consider a random graph of size n arising from one of the standard models, e.g., Erd\"os-Renyi random graph, random d-regular graph, or random graph with a given degree sequence. A random walker starts from a randomly chosen vertex and follows an independent random walk by choosing a random neighbor at each time step. For multiple walkers, whoever arrives first at a vertex gains that vertex. Using simulation, we will try to understand the random walk range process; and find suitable strategies to beat the random walk and gain as many vertices as possible.