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

ランダム木の高さと幅の積に関する厳密な普遍界

基本情報

論文ID: 2501.00458
タイトル: Tight universal bounds on the height times the width of random trees
著者: Serte Donderwinkel, Robin Khanfir
分類: math.PR（確率論）、math.CO（組合数学）
発表日: 2024年12月31日
論文リンク: 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変換を利用して2つの符号化を接続
交換可能橋の範囲性質を分析

ステップ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}$