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

Wennie W.J. Ma; Kathy Q. Ji

In the authors' words

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.

Main resultThe abstract does not state a limitation.

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

In the authors' words

More on Probability that day

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