文章基本信息

标题：On the independence number of some random trees
本地全文：下载
作者：Svante Janson
期刊名称：Electronic Communications in Probability
印刷版ISSN：1083-589X
出版年度：2020
卷号：25
DOI：10.1214/20-ECP345
语种：English
出版社：Electronic Communications in Probability
摘要：We show that for many models of random trees, the independence number divided by the size converges almost surely to a constant as the size grows to infinity; the trees that we consider include random recursive trees, binary and $m$-ary search trees, preferential attachment trees, and others. The limiting constant is computed, analytically or numerically, for several examples. The method is based on Crump–Mode–Jagers branching processes.
关键词：independence number;random trees;random recursive tree;binary search tree;Crump–Mode–Jagers branching process