Combinatorics

Speaker: Asaf Nachmias (TAU)
Title: The connectivity of the uniform spanning forest on planar graphs
Abstract:
The free uniform spanning forest (FUSF) of an infinite connected graph G is obtained as the weak limit uniformly chosen spanning trees of finite subgraphs of G. It is easy to see that the FUSF is supported on spanning graphs of G with no cycles, but it need not be connected. Indeed, a classical result of Pemantle ('91) asserts that when G=Z^d, the FUSF is almost surely a connected tree if and only if d=1,2,3,4.
We will show that the FUSF is almost surely connected on any bounded degree proper planar graph, answering a question of Benjamini, Lyons, Peres and Schramm ('01). An essential part of the proof is Koebe's circle packing theorem ('36) stating that any planar graph can be drawn in the plane so that vertices correspond to circles with disjoint interiors and neighboring vertices are tangent.
Joint work with Tom Hutchcroft

Date: 

Mon, 22/02/2016 - 10:30 to 12:30
Repeats every week every Monday until Sun Feb 28 2016

Location: 

B221 Rothberg (CS and Engineering building)