Combinatorics Seminar

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

Abstract:

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.