Probability

Speaker: 
Jonathan Hermon
Speaker Affiliation: 
UBC

November 19, 2025

ESB 2012
Canada

View All Events

Abstract: 

The effective resistance satisfies the triangle inequality and thus defines a metric. For finite graphs, this metric contains all of the information about the expected hitting times between pairs of vertices as well as about the cover time of the graph (= the first time by which every vertex has been visited at least once).

We show that for transitive graphs, the effective resistance between a pair of vertices o and x, which are at distance r from one another, is comparable (up to a constant multiplicative factor, depending only on the degree) to the expected number of returns to the origin by time r2. We use this (in the transitive bounded degree setup) to:

(1) Prove that every finite vertex-transitive graphs is quasi-isometric to a product of 3 cycles w.r.t. the effective resistance metric, where the constants in the quasi-isometry depend only on the degree.
(2) Give simple formulas, involving few natural geometric quantities, for the orders of the expected cover time and the maximal (over all pairs) effective resistance between a pair of vertices, as well as between arbitrary pairs of distance r (as a function of r and the natural geometric quantities).

Joint work with Lucas Teyssier (UBC) and Matt Tointon (U. Bristol).

Event Topic: