论文标题
随机树具有高度$ o（\ sqrt {n}）$
Random trees have height $O(\sqrt{n})$
论文作者
论文摘要
我们为具有给定学位序列的均匀随机树的高度获得了新的非反应尾巴界限，简单地产生了树木和条件的BienayMé树（分支过程的家族树），在解决Janson（2012）的三个猜想的过程中，并回答了文献中的其他几个问题。 此外，我们在度序列上定义了部分排序，并表明它在具有给定度序列的均匀随机树的高度上诱导了随机排序。后一个结果也可以用来表明次二元随机树是随机的最高树，具有给定数量的顶点和叶子（因此，随机二进制树是随机上最高的随机同源性，具有给定数量的顶点）。 我们的证明部分基于Foata和Fuchs（1970）引入的树木和序列之间的两者，可以重新铸造，以提供带有给定顶点度的随机树的线构造，如Addario-Berry，Blanc-Renaudie，Donderwinkel，Maazoun，Maazoun，Maazoun和Martin（20233）所示。
We obtain new non-asymptotic tail bounds for the height of uniformly random trees with a given degree sequence, simply generated trees and conditioned Bienaymé trees (the family trees of branching processes), in the process settling three conjectures of Janson (2012) and answering several other questions from the literature. Moreover, we define a partial ordering on degree sequences and show that it induces a stochastic ordering on the heights of uniformly random trees with given degree sequences. The latter result can also be used to show that sub-binary random trees are stochastically the tallest trees with a given number of vertices and leaves (and thus that random binary trees are the stochastically tallest random homeomorphically irreducible trees with a given number of vertices). Our proofs are based in part on the bijection between trees and sequences introduced by Foata and Fuchs (1970), which can be recast to provide a line-breaking construction of random trees with given vertex degrees as shown in Addario-Berry, Blanc-Renaudie, Donderwinkel, Maazoun and Martin (2023).
