Brownian approximation to counting graphs

DOI10.1137/120863769MaRDI QIDQ4899055zbMATH OpenOpenAlexFDO

Authors Soumik Pal

Publication date 4 January 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.5909

zbMATH Keywords

area under Brownian excursioncounting graphsWright's formula

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Abstract: Let C(n,k) denote the number of connected graphs with n labeled vertices and n+k-1 edges. For any sequence (k_n), the limit of C(n,k_n) as n tends to infinity is known. It has been observed that, if k_n=o(sqrt{n}), this limit is asymptotically equal to the $k_n$th 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 k_n=o(sqrt[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 Komlos, Major, and Tusnady.

Recommendations

• Enumerating graphs and Brownian motion
• scientific article; zbMATH DE number 1552347
• Counting connected graphs asymptotically
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• Brownian excursion area, wright's constants in graph enumeration, and other Brownian areas

Cited in

(2)

• Enumerating graphs and Brownian motion
• scientific article; zbMATH DE number 1552347 (Why is no real title available?)

This page was built for publication: Brownian approximation to counting graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899055)