On the coalescence time of reversible random walks

ABSTRACT: Start a continuous-time random walk from each vertex of a connected graph G. These walks evolve independently, except that, when two of them meet at a vertex, they coalesce into one. How long does it take until all walks have coalesced? We prove the expected full coalescence time is at most a universal constant times the largest expected hitting time of a vertex by a single random walk. This had been conjectured by Aldous and Fill in the early 90's.

(Journal reference: Trans. Amer. Math. Soc. 364 (2012), 2109-2128)

BIO:
Roberto Imbuzeiro Oliveira joined the faculty of IMPA in 2006 and was promoted to associate professor status in 2011. His interests lie in Probability, Discrete Mathematics and their connections with other fields, such as Statistics and Quantum Information. Prior to his appointment at IMPA, Roberto obtained a BSc degree from PUC-Rio (1999), a MSc degree from IMPA (2000) and a PhD degree from NYU (2004), where he was advised by Joel Spencer. From 2004 to 2006 he was at the IBM TJ Watson Research Center as a post-doc in their Physics of Information group.