Abstract:

In the random geometric graph process random points are embedded consecutively in the d-dimensional unit torus and every two points at distance at most $r$ form an edge. In the first part of the talk, we will explore analogues of well-known hitting time results for connectivity and Hamiltonicity in the Erdős–Rényi graph process when $r$ approaches $0$. The main focus of the talk will fall on a discussion of a geometric version of the power of choice where, at each step, an agent is shown two independent random points and is allowed to choose one of them. Related sharp threshold and hitting time results will be considered in an online and an offline version of the choice process.

Joint work with Dawid Ignasiak.