Uniform spanning trees of dense graphs

Uniform spanning trees of dense graphs

-
Asaf Nachmias, Tel Aviv University

We will present two theorems concerning the global and local structure of a uniform spanning tree (UST) of a connected simple graph with degrees linear in the number of vertices. The first theorem states that the diameter of the UST on such graphs is of order square root of the number of vertices with high probability. The second theorem provides the asymptotic frequency of the appearance of any small subtree (i.e., the local limit of the UST) in terms of the associated graphon. The proof of both theorems illustrates how to combine Szemeredi-like partition theorems with Kirchhoff's electric network theory.

Based on joint works with Noga Alon and Matan Shalev and with Jan Hldaky and Tuan Tran.