On the limiting distribution of the number of improper edges for random trees

Wennie W.J. Ma; Kathy Q. Ji

On the limiting distribution of the number of improper edges for random trees

Wennie W.J. Ma, Kathy Q. Ji

Preprint

En palabras de los autores

Improper edges were introduced by Shor to refine Cayley's formula for rooted labeled trees. Zeng established a connection between Shor's refinement and the Ramanujan polynomials. Let $T_{n}$ denote the set of rooted labeled trees on $[n] = {1, \dots, n}$ . We prove that the number of improper edges in a uniformly random tree in $T_{n}$ is asymptotically normal as $n \to \infty$ , with mean and variance asymptotic to $μ n$ and $σ^{2} n$ , respectively, where $μ = e - 2$ and $σ^{2} = e^{2} - 3 e + 1$ . This phenomenon was observed by Chen, and the proof presented here was developed through human--AI collaboration.

Resultado principalEl resumen no menciona limitaciones.

Leer el paper PDF

Apareció: miércoles, 23 de septiembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 15 pages, 1 figure

On the limiting distribution of the number of improper edges for random trees

En palabras de los autores

Más de Probabilidad ese día

The Most Informative Bit and Beyond: A Proof of the Courtade--Kumar Conjecture and Multibit Extensions

Sample-Based Prophet Inequalities for Random Walks

Repeated averaging on expanders I: random d-regular graph

Counterexamples to the Ramos conjecture for two hyperplanes

Concentration of Regularized Sparse Random Matrices: Spectral Edge Bounds via Nonbacktracking Operators

Repeated averaging on expanders I: random $d$ -regular graph