For finite-type inhomogeneous random graphs, component-density fluctuations converge to a Gaussian process solving an explicit infinite-dimensional SDE, yielding CLTs for the giant component and MST weight.
Random minimum spanning tree and dense graph limits
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
A theorem of Frieze from 1985 asserts that the total weight of the minimum spanning tree of the complete graph $K_n$ whose edges get independent weights from the distribution $UNIFORM[0,1]$ converges to Ap\'ery's constant in probability, as $n\to\infty$. We generalize this result to sequences of graphs $G_n$ that converge to a graphon $W$. Further, we allow the weights of the edges to be drawn from different distributions (subject to moderate conditions). The limiting total weight $\kappa(W)$ of the minimum spanning tree is expressed in terms of a certain branching process defined on $W$, which was studied previously by Bollob\'as, Janson and Riordan in connection with the giant component in inhomogeneous random graphs.
citation-role summary
citation-polarity summary
fields
math.PR 1years
2024 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Functional Central limit theorems for microscopic and macroscopic functionals of inhomogeneous random graphs
For finite-type inhomogeneous random graphs, component-density fluctuations converge to a Gaussian process solving an explicit infinite-dimensional SDE, yielding CLTs for the giant component and MST weight.