Competition with Random Walk on Random Graphs

Faculty Member

Partha Dey and Daesung Kim

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.

Team Meetings

Weekly

Project Difficulty

Intermediate

Undergrad Prerequisites

Math 461 (Probability Theory), Math 416 (Linear algebra), Python