BROWNIAN APPROXIMATION TO COUNTING GRAPHS SOUMIK PAL

Abstract. Let C(n, k) denote the number of connected graphs with n labeled vertices and n+ k − 1 edges. For any sequence (kn), the limit of C(n, kn) as n tends to infinity is known. It has been observed that, if kn = o( n), this limit is asymptotically equal to the knth moment of the area under the standard Brownian excursion. These moments have been computed in the literature via independent methods. In this article we show why this is true for kn = o ( 3 n) starting from an observation made by Joel Spencer. The elementary argument uses a result about strong embedding of the Uniform empirical process in the Brownian bridge proved by Komlós, Major, and Tusnády. 1