UBC Probability Seminar: Yinon Spinka

A Lipschitz function on a graph G is a function f:V->Z from the vertex set of the graph to the integers which changes by at most 1 along any edge of the graph. Given a finite connected graph G, and fixing the value of the function to be 0 on at least one vertex, we may sample such a Lipschitz function uniformly at random. What can we say about the typical height at a vertex? This depends heavily on G. For example, when G is a path of length n, and the height at one of the endpoints is fixed to be 0, this model corresponds to a simple random walk with uniform increments in {-1,0,1}, and hence the height at the opposite endpoint of the path is typically of order sqrt(n). In this talk, we consider the case when G is a finite tree (to be thought of an infinite tree pruned at a given depth), and the height at the leaves is fixed to be 0. We would like to understand the distribution of the height at the root. We first discuss the issue of declocalization vs localization (i.e., tightness of the height as the depth of the tree increases), showing that the height function is localized on any transient tree. We then discuss the question of whether the height at the root converges in distribution on a d-ary tree, showing that there is a phase transition in d.

Based on joint works with Nathaniel Butler, Alon Heller, Kesav Krishnan and Gourab Ray.