Normal convergence problem? Two moments and a recurrence may be the clues (Q1578596): Difference between revisions

Certain random variables assigned to labelled rooted trees are asymptotically normally distributed. This challenging but rewarding paper develops some convergence results: 1. If \(X_n =\) the independence number of an \(n\)-tree, the result of \textit{A. Meir} and \textit{J. W. Moon} [Nederl. Akad. Wet., Proc., Ser. A 76, 335-341 (1973; Zbl 0264.05104)] that \(X_n\) is asymptotically normal is tightened. Two versions of the independence number are investigated, and result in estimates of the mean to within \(O(n^{-1})\) and variance to within \(O(1)\). 2. If \(Z_{n,k} =\) the number of \((k+1)\)-degree vertices in a random \(n\)-tree, then the vector \({\mathbf Z}_n\) is asymptotically Gaussian. This result extends the result of \textit{A. Rényi} [Publ. Math. Inst. Hung. Acad. Sci. 4, 73-85 (1959; Zbl 0093.37604)] that \(Z_{n,1}\) is asymptotically normal. 3. If \(Y_n =\) the number of extensions of an \(n\)-tree to a linear order, then \(L_n = \log (Y_n/n!)\) is asymptotically normal. The estimate of the mean is within \(O(n^{-1/2} \log n)\) and variance within \(O(n^{1/2} \log n)\). These results are developed by a careful analysis of the moment generating functions using a variety of techniques, from recurrences to contour integration.