Asymptotics of trees with a prescribed degree sequence and applications
Asymptotics of trees with a prescribed degree sequence and applications
复制标题
具有规定度数序列的树的渐近性及其应用
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
M. Hannington
中科院分区：
文献类型：
--
作者：
K. Poulsen;M. Hannington
令 t 为有根树，nbi(t) 为 t 中具有 i 个子节点的节点数。 t的度序列(ni(t),i≥0)满足 Σi≥0ni(t)=1+Σi≥0ini(t)=|t| ，其中 |t|表示 t 中的节点数。在本文中，我们考虑在具有相同度序列 s 的所有平面树中均匀采样的树；我们将 ℙs 写为相应的分布。设 s(κ)=(ni(κ),i≥0) 是由 κ 索引的度序列列表，对应于大小为 nκ→+∞ 的树。我们证明，在 (s(κ),κ>0) 的一些简单且自然的假设下，在 ℙs(κ) 下采样的树在通过 nκ1/2 归一化后收敛到布朗连续随机树。提供了一些有关 Galton–Watson 树和聚结过程的应用。版权所有 © 2012 Wiley periodicals, Inc. Random Struct。阿尔格., 44, 290‐316, 2014
Let t be a rooted tree and nbi(t) the number of nodes in t having i children. The degree sequence (ni(t),i≥0) of t satisfies ∑i≥0ni(t)=1+∑i≥0ini(t)=|t| , where |t| denotes the number of nodes in t. In this paper, we consider trees sampled uniformly among all plane trees having the same degree sequence s ; we write ℙs for the corresponding distribution. Let s(κ)=(ni(κ),i≥0) be a list of degree sequences indexed by κ corresponding to trees with size nκ→+∞ . We show that under some simple and natural hypotheses on (s(κ),κ>0) the trees sampled under ℙs(κ) converge to the Brownian continuum random tree after normalisation by nκ1/2 . Some applications concerning Galton–Watson trees and coalescence processes are provided.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 290‐316, 2014