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

Basic Information

• Paper ID: 2501.00458
• Title: Tight universal bounds on the height times the width of random trees
• Authors: Serte Donderwinkel, Robin Khanfir
• Classification: math.PR (Probability Theory), math.CO (Combinatorics)
• Publication Date: December 31, 2024
• Paper Link: https://arxiv.org/abs/2501.00458

Abstract

This paper establishes assumption-free, non-asymptotic, and uniform bounds on the product of height and width for uniformly random trees with given degree sequences, conditioned Bienaymé trees, and simply generated trees. The authors prove that for trees of size $n$, this product is $O(n \log n)$ in probability, answering a question posed by Addario-Berry (2019). The order of the bound is tight.

Research Background and Motivation

Problem Background

1. Core Problem: Investigating upper bounds on the product of height and width of random trees. For a rooted tree $t$, the height $Ht(t)$ is the maximum distance from the root to any node, and the width $Wd(t)$ is the maximum number of nodes in any level.
2. Significance: Height and width provide a rough description of the global shape of a tree and represent a first step in studying the geometric properties of trees. Magnitude estimates of these statistics are crucial for understanding the geometric structure of various random tree models.
3. Existing Limitations:
   • Previous research primarily studied height and width separately, lacking unified analysis of their product
   • Existing results typically require specific assumptions on offspring distributions (e.g., finite variance)
   • Lack of non-asymptotic uniform bounds
4. Research Motivation: Addario-Berry posed an open question in 2019: whether there exists an offspring distribution such that $Wd(T_{\mu,n})Ht(T_{\mu,n})/n$ is significantly larger than $\log n$ with non-vanishing probability? This paper provides a negative answer.

Core Contributions

1. Assumption-Free Uniform Bounds: For any offspring distribution $\mu$ and any $n$, the authors prove that $P(Wd(T_{\mu,n})Ht(T_{\mu,n}) > sn \log n) \leq 230s^{-2/13}$
2. Broad Applicability: Results apply to multiple random tree models:
   • Conditioned Bienaymé trees
   • Simply generated trees
   • Uniformly random trees with given degree sequences
3. Tightness Proof: Through known examples, the authors demonstrate that the $O(n \log n)$ bound is tight
4. Elementary Proof Methods: Uses relatively simple probabilistic techniques, avoiding complex analytical tools

Methodology Details

Problem Setup

Given a type sequence $n = (n_i)_{i \geq 0}$, where $n_i$ denotes the number of vertices with $i$ children, the authors study the probability bounds on the product of height $Ht(T)$ and width $Wd(T)$ of a uniformly random plane tree $T$.

Core Technical Framework

1. Spinal Decomposition

For a vertex $u$ in tree $t$, define the spinal weight:

• $S_u(t) = \#\{v \in t \setminus \{\emptyset\} : \overleftarrow{v} = u \wedge v \text{ and } \overleftarrow{v} \neq u\}$
• $S^d_u(t)$: right spinal weight (younger siblings)
• $S^g_u(t)$: left spinal weight (older siblings)

2. Second-Order Height

Define second-order height: $Ht^{(2)}(t) = \max_{u,v \in t} \min(|u| - |u \wedge v|, |v| - |u \wedge v|)$

Key property: $Ht^{(2)}(t) = \max_{v \in t} |v| - |u \wedge v|$, where $|u| = Ht(t)$

3. Tree Encoding

Encode trees as random walks using depth-first and breadth-first traversals:

• Depth-first walk: $X^{df}_i(t) = S^d_{u^{df}_i(t)}(t)$
• Breadth-first walk: Related to width

Main Proof Strategy

Step 1: Height Comparison (Proposition 2.3)

Prove that for $\epsilon > 0$, if $\epsilon^{1/3}n_0 \geq 2$: $P(\epsilon Ht(T) \geq 1; \epsilon Ht(T) > Ht^{(2)}(T)) \leq 64\epsilon^{1/3}$

Technical Points:

• Construct type-preserving mappings converting linear trees to branching trees
• Use cyclic shift techniques to analyze ancestral lineages

Step 2: Width Comparison (Proposition 2.4)

Prove that if $\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}$

Technical Points:

• Utilize Vervaat transformation to connect two encodings
• Analyze range properties of exchangeable bridges

Step 3: Spinal Height Control (Proposition 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}$

Technical Points:

• Stochastic domination arguments
• Reduce problem to maximum height analysis of path forests

Step 4: Symmetrization (Propositions 2.6, 2.7)

Eliminate left-right asymmetry through shuffling operations:

• Mirror shuffling preserves tree distribution
• Exploit randomness of planar ordering

Experimental Setup

Theoretical Verification

This is purely theoretical work, verified primarily through mathematical proofs:

1. Tightness Examples: Reference results from Kortchemski (2014) and Addario-Berry (2019), demonstrating the existence of offspring distributions where $Wd(T_{\mu,n})Ht(T_{\mu,n})$ achieves $\Theta(n \log n)$
2. Special Case Analysis:
   • Finite variance case: $Ht(T_{\mu,n}) \sim \sqrt{n}$, $Wd(T_{\mu,n}) \sim \sqrt{n}$
   • Heavy-tailed distribution case: Condensation phenomenon occurs, leading to $O(n \log n)$ behavior

Experimental Results

Main Results

Theorem 1.1 (Bienaymé Trees)

For any offspring distribution $\mu$ and $n \geq 3$: $P(Wd(T_{\mu,n})Ht(T_{\mu,n}) > sn \log n) \leq 230s^{-2/13}$

Theorem 1.2 (Simply Generated Trees)

For any weight sequence $w$ and $n \geq 3$: $P(Wd(T_{w,n})Ht(T_{w,n}) > sn \log n) \leq 230s^{-2/13}$

Theorem 1.3 (Trees with Given Degree Sequences)

For any degree sequence $d$ satisfying $\sum_{i=1}^n d_i = n-1$: $P(Wd(T_d)Ht(T_d) > sn \log n) \leq 230s^{-2/13}$

Technical Results

Range Bounds for Exchangeable Bridges (Theorem 4.5)

For jump sequences $b^n$, the sequence $(\sigma_n^{-1}R(Y^n))_{n \geq 1}$ is tight, where $\sigma_n = \sqrt{\sigma^2(b^n)}$.

Specifically:

• Upper Bound (Proposition 4.6): $P(\sigma^{-1}R(Y) \geq \epsilon^{-1}) \leq 12\epsilon$
• Lower Bound (Proposition 4.8): $P(2\sigma^{-1}R(Y) \leq p^{-1/2}) \leq 400p^{-1}$

Related Work

Historical Development

1. Classical Results: Kolchin (1986) proved asymptotic behavior in the finite variance case
2. Scaling Limits: Aldous (1993), Duquesne (2003) and others established continuous limits
3. Non-Asymptotic Bounds: Devroye-Janson-Addario-Berry (2013), Kortchemski (2015)

Innovations in This Paper

1. Assumption-Free: No assumptions required on offspring distributions
2. Unified Treatment: Simultaneously handles height and width
3. Elementary Methods: Avoids complex analytical tools

Conclusions and Discussion

Main Conclusions

1. For random trees of size $n$, the product of height and width almost surely does not exceed $O(n \log n)$
2. This bound holds for all considered random tree models without any assumptions
3. The bound is tight, with examples achieving this order

Limitations

1. Tail Exponent: The exponent $2/13$ is far from optimal and may be improved through finer analysis
2. Constants: The constant 230 may not be optimal
3. Method Limitations: Uses second-moment methods; higher-order moments might yield improvements

Future Directions

The paper poses three open problems:

1. Compute the value of \sup E[1_{\{#T_\mu < \infty\}}Ht(T_\mu)Wd(T_\mu)(#T_\mu)^{-1}]
2. Characterize conditions under which $Ht(T_{\mu,n})Wd(T_{\mu,n}) = \Theta(n)$ and $= \Theta(n \log n)$
3. For slowly varying functions $f(n)$, whether there exists an offspring distribution such that the product is $\Theta(nf(n))$

In-Depth Evaluation

Strengths

1. Important Problem: Resolves an important open problem posed by Addario-Berry
2. Technical Innovation:
   • Clever spinal decomposition techniques
   • Application of exchangeable bridge theory
   • Symmetrization tricks using shuffling operations
3. Broad Applicability: Results apply to multiple random tree models
4. Elementary Methods: Proofs are relatively concise, avoiding complex tools

Weaknesses

1. Tail Bounds: The decay rate $s^{-2/13}$ is relatively slow, potentially insufficient for practical applications
2. Constants: The constant 230 is large, limiting practical significance
3. Technical Density: Some proof steps are highly technical, lacking intuitive explanations

Impact

1. Theoretical Contribution: Provides important results for random tree geometry theory
2. Methodological Value: Spinal decomposition and shuffling techniques may have broader applications
3. Open Problems: Proposed questions guide future research directions

Application Scenarios

1. Theoretical Research: Random tree and random graph theory
2. Algorithm Analysis: Complexity analysis of tree algorithms
3. Statistical Physics: Branching processes, percolation theory

References

Key references include:

• Addario-Berry (2019): Posed the original problem
• Kortchemski (2014, 2015): Provided tightness examples and technical foundations
• Aldous (1993): Continuous random tree theory
• Devroye-Janson-Addario-Berry (2013): Pioneering work on non-asymptotic bounds

This paper represents important theoretical work at the intersection of probability theory and combinatorics, solving a fundamental yet difficult problem through clever probabilistic techniques and making substantial contributions to random tree theory.