Scholarlink

<p>Inspired by Stufler’s recent probabilistic proof of Otter’s asymptotic number of unlabeled trees, we revisit work of Palmer and Schwenk, and study unlabeled forests from a probabilistic point of view. We show that the number of trees in a random forest converges, with all of its moments, to a shifted compound Poisson. We also find the asymptotic proportion of forests that are trees. The key fact is that the number of trees and the number of forests are related by a Lévy process. As such, the results by Palmer and Schwenk follow by an earlier and far-reaching limit theory by Hawkes and Jenkins. We also show how this limit theory implies results by Schwenk and by Meir and Moon, related to degrees in large random trees. Our arguments apply, more generally, to the enumeration of subexponentially weighted integer partitions, or, in fact, any setting where the underlying Lévy process follows the one big jump principle.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

To See the Forest for the Trees: On the Infinite Divisibility of Unlabeled Forests

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月29日

查看全文
  • Michal Bassan,
  • Serte Donderwinkel,
  • Brett Kolesnik

摘要

Inspired by Stufler’s recent probabilistic proof of Otter’s asymptotic number of unlabeled trees, we revisit work of Palmer and Schwenk, and study unlabeled forests from a probabilistic point of view. We show that the number of trees in a random forest converges, with all of its moments, to a shifted compound Poisson. We also find the asymptotic proportion of forests that are trees. The key fact is that the number of trees and the number of forests are related by a Lévy process. As such, the results by Palmer and Schwenk follow by an earlier and far-reaching limit theory by Hawkes and Jenkins. We also show how this limit theory implies results by Schwenk and by Meir and Moon, related to degrees in large random trees. Our arguments apply, more generally, to the enumeration of subexponentially weighted integer partitions, or, in fact, any setting where the underlying Lévy process follows the one big jump principle.