Where do (random) trees grow leaves?

We study a model of random binary trees grown “by the leaves" in the style of Luczak and Winkler [LW04]. If <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>τ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> is a uniform plane binary tree of size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>n</mml:mi> </mml:math> , Luczak and Winkler, and later explicitly Caraceni and Stauffer, constructed a measure <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ν</mml:mi> <mml:msub> <mml:mi>τ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:msub> </mml:math> such that the tree obtained by adding a cherry on a leaf sampled according to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ν</mml:mi> <mml:msub> <mml:mi>τ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:msub> </mml:math> is still uniformly distributed on the set of all plane binary trees with size <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . It turns out that the measure <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ν</mml:mi> <mml:msub> <mml:mi>τ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:msub> </mml:math> , which we call the leaf-growth measure, is noticeably different from the uniform measure on the leaves of the tree <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>τ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> . In fact we prove that, as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi> </mml:mrow> </mml:math> , with high probability it is almost entirely supported by a subset of only <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>3</mml:mn> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>2</mml:mn> <mml:mo>-</mml:mo> <mml:msqrt> <mml:mn>3</mml:mn> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:msup> <mml:mo>≈</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo>.</mml:mo> <mml:mn>8038</mml:mn> <mml:mo>.</mml:mo> <mml:mo>.</mml:mo> <mml:mo>.</mml:mo> </mml:mrow> </mml:msup> <mml:mspace width="4pt"/> <mml:mtext>leaves</mml:mtext> </mml:mrow> </mml:math> . In the continuous setting, we construct the scaling limit of uniform binary trees equipped with this measure, which is the Brownian Continuum Random Tree equipped with a probability measure supported by a fractal set of dimension <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>6</mml:mn> <mml:mo>(</mml:mo> <mml:mn>2</mml:mn> <mml:mo>-</mml:mo> <mml:msqrt> <mml:mn>3</mml:mn> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We also compute the full (discrete) multifractal spectrum. This work is a first step towards understanding the diffusion limit of the discrete leaf-growth procedure.