2025-11-10T02:30:54.908722

Tight universal bounds on the height times the width of random trees

Donderwinkel, Khanfir

We obtain assumption-free, non-asymptotic, uniform bounds on the product of the height and the width of uniformly random trees with a given degree sequence, conditioned BienaymÃ© trees and simply generated trees. We show that for a tree of size $n$, this product is $O(n \log n)$ in probability, answering a question by Addario-Berry (2019). The order of this bound is tight in this generality.

academic

Tight universal bounds on the height times the width of random trees

基本信息

论文ID: 2501.00458
标题: Tight universal bounds on the height times the width of random trees
作者: Serte Donderwinkel, Robin Khanfir
分类: math.PR (概率论), math.CO (组合数学)
发表时间: December 31, 2024
论文链接: https://arxiv.org/abs/2501.00458

摘要

本文获得了对给定度序列的均匀随机树、条件Bienaymé树和简单生成树的高度与宽度乘积的无假设、非渐近、一致界。我们证明了对于大小为 $n$ 的树，这个乘积在概率意义下是 $O(n \log n)$ ，回答了Addario-Berry (2019)提出的问题。该界的阶是紧的。

研究背景与动机

问题背景

核心问题: 研究随机树的高度(height)与宽度(width)乘积的上界。对于根树 $t$ ，高度 $Ht(t)$ 是从根到任意节点的最大距离，宽度 $Wd(t)$ 是任意层中节点数的最大值。
重要性: 高度和宽度给出了树的全局形状的粗略描述，是研究树几何性质的第一步。这些统计量的量级估计对理解各种随机树模型的几何结构至关重要。
现有局限性:
- 以往研究主要分别研究高度和宽度，缺乏对它们乘积的统一分析
- 现有结果通常需要对后代分布做特定假设(如有限方差)
- 缺乏非渐近的一致界
研究动机: Addario-Berry在2019年提出了一个开放问题：是否存在后代分布使得 $Wd(T_{\mu,n})Ht(T_{\mu,n})/n$ 比 $\log n$ 大很多且概率不消失？本文给出了否定答案。

核心贡献

无假设一致界: 对任意后代分布 $\mu$ 和任意 $n$ ，证明了 $P(Wd(T_{\mu,n})Ht(T_{\mu,n}) > sn \log n) \leq 230s^{-2/13}$
广泛适用性: 结果适用于多种随机树模型：
- 条件Bienaymé树
- 简单生成树
- 给定度序列的均匀随机树
紧性证明: 通过已知例子证明 $O(n \log n)$ 界是紧的
初等证明方法: 使用相对简单的概率技术，避免了复杂的分析工具

方法详解

任务定义

给定类型序列 $n = (n_i)_{i \geq 0}$ ，其中 $n_i$ 表示有 $i$ 个子节点的顶点数量，研究均匀随机平面树 $T$ 的高度 $Ht(T)$ 与宽度 $Wd(T)$ 乘积的概率界。

核心技术框架

1. 脊柱分解(Spinal Decomposition)

对于树 $t$ 中的顶点 $u$ ，定义脊柱权重：

$S_u(t) = \#\{v \in t \setminus \{\emptyset\} : \overleftarrow{v} = u \wedge v \text{ and } \overleftarrow{v} \neq u\}$
$S^d_u(t)$ ：右脊柱权重(younger siblings)
$S^g_u(t)$ ：左脊柱权重(older siblings)

2. 二阶高度

定义二阶高度： $Ht^{(2)}(t) = \max_{u,v \in t} \min(|u| - |u \wedge v|, |v| - |u \wedge v|)$

关键性质： $Ht^{(2)}(t) = \max_{v \in t} |v| - |u \wedge v|$ ，其中 $|u| = Ht(t)$

3. 树的编码

使用深度优先遍历和广度优先遍历将树编码为随机游走：

深度优先游走： $X^{df}_i(t) = S^d_{u^{df}_i(t)}(t)$
广度优先游走：与宽度相关

主要证明策略

步骤1: 高度比较(命题2.3)

证明对于 $\epsilon > 0$ ，如果 $\epsilon^{1/3}n_0 \geq 2$ ： $P(\epsilon Ht(T) \geq 1; \epsilon Ht(T) > Ht^{(2)}(T)) \leq 64\epsilon^{1/3}$

技术要点:

构造类型保持映射，将线状树转换为叉状树
使用循环移位技术分析祖先谱系

步骤2: 宽度比较(命题2.4)

证明如果 $\epsilon^{4/3}\sqrt{n_0} - 1 \geq 26$ ： $P(\epsilon Wd(T) \geq \max_u S^d_u(T)) \leq 3\sqrt{222}\epsilon^{2/3}$

技术要点:

利用Vervaat变换连接两种编码
分析可交换桥的范围性质

步骤3: 脊柱高度控制(命题2.5)

$P\left(\max_{u,v \in T, u \leq v} (|v| - |u \wedge v|)S^d_u(T) \geq sn \log n\right) \leq 3n^{2-s/2}$

技术要点:

随机占优论证
将问题归约到路径森林的最大高度分析

步骤4: 对称化(命题2.6, 2.7)

通过混洗操作消除左右不对称性：

镜像混洗保持树的分布
利用平面顺序的随机性

实验设置

理论验证

本文为纯理论工作，主要通过数学证明验证结果：

紧性例子: 引用Kortchemski (2014)和Addario-Berry (2019)的结果，证明存在后代分布使得 $Wd(T_{\mu,n})Ht(T_{\mu,n})$ 达到 $\Theta(n \log n)$
特殊情况分析:
- 有限方差情况： $Ht(T_{\mu,n}) \sim \sqrt{n}$ , $Wd(T_{\mu,n}) \sim \sqrt{n}$
- 重尾分布情况：出现凝聚现象，导致 $O(n \log n)$ 行为

上界(命题4.6): $P(\sigma^{-1}R(Y) \geq \epsilon^{-1}) \leq 12\epsilon$
下界(命题4.8): $P(2\sigma^{-1}R(Y) \leq p^{-1/2}) \leq 400p^{-1}$