论文标题
树/内臂射击和浓度不平等
Tree/Endofunction Bijections and Concentration Inequalities
论文作者
论文摘要
我们展示了一种在$ n $顶点上证明均匀随机树的精确浓度不平等的方法，其中$ n \ geq1 $是固定的正整数。该方法使用映射$ f \ colon \ {1，\ ldots，n \} \ to \ {1，\ ldots，n \} $与$ n $ dertices上的双扎树。主要应用程序是连接到均匀随机树中独立集的顶点数量的浓度不等式，然后将其用于证明其独立设定序列的部分非模态。因此，我们为经常使用组合论点的不平等提出了概率论点。
We demonstrate a method for proving precise concentration inequalities in uniformly random trees on $n$ vertices, where $n\geq1$ is a fixed positive integer. The method uses a bijection between mappings $f\colon\{1,\ldots,n\}\to\{1,\ldots,n\}$ and doubly rooted trees on $n$ vertices. The main application is a concentration inequality for the number of vertices connected to an independent set in a uniformly random tree, which is then used to prove partial unimodality of its independent set sequence. So, we give probabilistic arguments for inequalities that often use combinatorial arguments.
