2014/07/31 by Louigi Addario-Berry, Louigi Addario‐Berry, Addario-Berry, Louigi · 1 citation
Mathematics · Physics and Astronomy · #60C05 #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Probability (math.PR) #Stochastic processes and statistical mechanics #math.PR #msc:60C05
paper · pdf · doi:10.48550/arxiv.1407.8538
42 pages, 4 figures, 25 exercises, 6 open problems
arxiv created 2014/07/31 · openalex publication_date 2014/07/31 · arxiv updated 2014/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In these expository notes, we describe some features of the multiplicative coalescent and its connection with random graphs and minimum spanning trees. We use Pitman's proof of Cayley's formula, which proceeds via a calculation of the partition function of the additive coalescent, as motivation and as a launchpad. We define a random variable which may reasonably be called the empirical partition function of the multiplicative coalescent, and show that its typical value is exponentially smaller than its expected value. Our arguments lead us to an analysis of the susceptibility of the Erdős-Rényi random graph process, and thence to a novel proof of Frieze's ζ(3)-limit theorem for the weight of a random minimum spanning tree.