Growing random trees, maps, and squarings

17 June 2014
Louigi Addario-Berry
<p>We use a growth procedure for binary trees due to Luczak and Winkler, a bijection between binary trees and irreducible quadrangulations of the hexagon due to Fusy, Poulalhon and Schaeffer, and the classical angular mapping between quadrangulations and maps, to define a growth procedure for maps. The growth procedure is local, in that every map is obtained from its predecessor by an operation that only modifies vertices lying on a common face with some fixed vertex. The sequence of maps has an almost sure limit G; we show that G is the distributional local limit of large, uniformly random 3-connected graphs. <br> A classical result of Brooks, Smith, Stone and Tutte associates squarings of rectangles to edge-rooted planar graphs. Our map growth procedure induces a growing sequence of squarings, which we show has an almost sure limit: an infinite squaring of a finite rectangle, which almost surely has a unique point of accumulation. We know almost nothing about the limit, but it should be in some way related to "Liouville quantum gravity". <br>Parts joint with Nicholas Leavitt. </p>
  • Combinatorial Theory Seminar