The effect of adding randomly weighted edges

NEW

Problem: Reconstructed conjecture. Let $G_n$ be a connected $d_n$-regular simple graph on $n$ vertices with $d_n/n\to\alpha\in(0,1]$. Give each edge an independent $U[0,1]$ weight, and let

The conjecture is

Together with the known lower bound $\operatorname{mst}(G_n)\ge(\zeta(3)-o(1))n/d_n$, this replaces the $+1$ in Frieze’s displayed inequality (3) by $+1/2$.

Result: The conjectured upper bound is true.

Use the standard Kruskal representation. For $p\in[0,1]$, let $G_p$ be the subgraph of edges of weight at most $p$. We use the following component estimate of Frieze–Ruszinkó–Thoma: for graphs of minimum degree $d\to\infty$, the expected total weight of all Kruskal edges selected while one of the two joined components has size at most $d$ is at most

and, for $p_0=C\log d/d$ with fixed large $C$,

Fix $p_0=C\log d_n/d_n=o(1)$. Let $F_0$ be the minimum spanning forest of $G_{p_0}$. Every Kruskal edge of $F_0$ either is of the small-component type above, or joins two components already both larger than $d_n$. The number of such large-large joins is deterministically at most $n/(d_n+1)$, since each large component contains more than $d_n$ vertices and large components, once born, only merge. Hence

Now contract the components of $G_{p_0}$. The contracted graph is connected. Conditional on $G_{p_0}$, every edge between distinct components has weight distributed independently as $U[p_0,1]$. Choose, deterministically from the contracted graph, any spanning tree of the contracted graph and add its corresponding original edges. Its conditional expected weight is

Moreover,

so

Therefore

Since $d_n/n\to\alpha$, this is exactly

The constant $1/2$ is best possible as a universal additive constant. Take $q$ copies of $K_{r+1}-e$, and connect the two deficient vertices in consecutive copies by a cycle of $q$ added edges. This graph is $r$-regular on $q(r+1)$ vertices, so $\alpha\to1/q$. The internal MST contribution is $q\zeta(3)+o(1)$, while the connecting cycle contributes the expected sum of the $q-1$ smallest of $q$ independent $U[0,1]$ variables, namely

After multiplying by $\alpha\sim1/q$, the extra additive constant tends to

as $q\to\infty$. Thus no smaller universal constant can replace $1/2$.

Citation: The small-component Kruskal estimates are those used by Frieze, Ruszinkó and Thoma, “A note on random minimum length spanning trees,” Electron. J. Combin. 7 (2000), R41. The $+1/2$ replacement follows from the argument above.