Uniformization of distributional limits of graphs

Опубликовано 24 июля 2017, 4:48

Benjamini and Schramm (2001) showed that distributional limits of finite planar graphs with uniformly bounded degrees are almost surely recurrent. The major tool in their proof is a lemma which asserts that for a limit of bounded-degree planar triangulations, the circle packing in the plane has at most one accumulation point. This fact has been shown to generalize to graphs that can be sphere packed in R^d (Benjamini-Curien 2011), but it is not clear whether it has consequences for the random walk when d > 2.

I will explain how the Benjamini-Schramm lemma suggests that one can uniformize the intrinsic metric on the underlying graph so that the volume growth of balls is at most d. The uniformized geometry allows us to recover the recurrence result, extend it to graphs with unbounded degrees, and carries significant consequences for the random walk. For instance, for graphs sphere-packed in R^d, the distributional limit almost surely has spectral dimension at most d.

See more on this video at microsoft.com/en-us/research/v...