Search ResultsShowing 1-2 of 2
-
arXiv:2310.11705 (Published 2023-10-18)
Random minimum spanning tree and dense graph limits
Comments: 20 pages, 1 figureA 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.
-
arXiv:2305.03607 (Published 2023-05-05)
Connectivity of inhomogeneous random graphs II
Comments: 20 pages, 3 figuresCategories: math.COEach graphon $W:\Omega^2\rightarrow[0,1]$ yields an inhomogeneous random graph model $G(n,W)$. We show that $G(n,W)$ is asymptotically almost surely connected if and only if (i) $W$ is a connected graphon and (ii) the measure of elements of $\Omega$ of $W$-degree less than $\alpha$ is $o(\alpha)$ as $\alpha\rightarrow 0$. These two conditions encapsulate the absence of several linear-sized components, and of isolated vertices, respectively. We study in bigger detail the limit probability of the property that $G(n,W)$ contains an isolated vertex, and, more generally, the limit distribution of the minimum degree of $G(n,W)$.