Combinatorics Seminar

When: Sunday, October 22, 10am
Where: Schreiber 309
Speaker: Asaf Nachmias, Tel Aviv University
Title: The uniform spanning tree of dense graphs


Let G be a connected graph in which almost all vertices have linear degrees and let T be a uniform spanning tree of G. For any fixed rooted tree F of height r>0 we compute the asymptotic density of vertices v for which the r-ball around v in T is isomorphic to F. 

As an application, we prove that in such dense graphs, with high probability, the density of leaves in a uniform spanning tree is at least e-1-o(1), the density of vertices of degree 2 is at most e-1+o(1), and the density of vertices of degree k>2 is at most ((k-2)/e)k-2/(k-1)!+o(1). These bounds are sharp.

Joint work with Jan Hladky and Tuan Tran.