Consider a dense Erdös-Rényi random graph with parameters n and p, with p fixed in (0,1). Let H_n(p) be the hitting time between two distinct vertices: run simple random walk from a vertex w, wait until it hits another vertex v, and average over the random walk. What does the distribution of H_n(p) look like? Heuristic from the physics literature suggests H_n(p) concentrates around n. Löwe and Terveer settled the question when the starting point is randomized according to the stationary distribution, showing also a central limit theorem for the fluctuations. In joint work with Steinerberger, we show that H_n(p) satisfies, with high probability and up to o(1) error, an extremely neat and simple formula. Easy corollaries include a central limit theorem for H_n(p) from any starting point (deterministic or random).

Speakers website