Asymptotics of trees with a prescribed degree sequence and applications. Issue 3 (5th September 2012) - Broutin, Nicolas; Marckert, Jean‐François
Abstract Let t be a rooted tree and nbi(t) the number of nodes in t having i children. The degree sequence <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s10bn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(ni(t), i≥0)</alternatives> of t satisfies <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s10c6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />∑i≥0ni(t)=1+∑i≥0ini(t)=|t|</alternatives>, where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s10dr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />|t|</alternatives> denotes the number of nodes in t. In this paper, we consider trees sampled uniformly among all plane trees having the same degree sequence <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s10f9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />s</alternatives>; we write <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s10vx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ℙs</alternatives> for the corresponding distribution. Let <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s10tc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />s(κ)=(ni(κ), i≥0)</alternatives> be a list of degree sequences indexed by κ corresponding to trees with size <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s10x1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />nκ→+∞</alternatives>. We show that under some simple and natural hypotheses on <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s10wg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(s(κ), κ>0)</alternatives> the trees sampled under <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s10zk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ℙs(κ)</alternatives> converge to the Brownian continuum random tree after normalisation by <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s114v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />nκ1/2</alternatives>. Some applications concerning Galton–Watson trees and coalescence processes are provided.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 290‐316, 2014