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)$ : 우측 척추 가중치(더 어린 형제)
$S^g_u(t)$ : 좌측 척추 가중치(더 나이 많은 형제)

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}$