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

$$\operatorname{mst}(G_n)=\mathbb E[\text{weight of the minimum spanning tree of }G_n].$$

The conjecture is

$$\operatorname{mst}(G_n)\le \left(\zeta(3)+\frac12+o(1)\right)\frac{n}{d_n} =\frac{\zeta(3)+1/2+o(1)}{\alpha}.$$

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

$$(\zeta(3)+o(1))\frac nd,$$

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

$$\mathbb E[\#\{\text{components of }G_{p_0}\text{ of size }\le d\}]=o(n/d).$$

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

$$\mathbb E w(F_0) \le (\zeta(3)+o(1))\frac n{d_n} +p_0\frac n{d_n+1} = (\zeta(3)+o(1))\frac n{d_n}.$$

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

$$\frac{1+p_0}{2}\bigl(\kappa(G_{p_0})-1\bigr).$$

Moreover,

$$\kappa(G_{p_0}) \le \frac n{d_n+1} + \#\{\text{components of }G_{p_0}\text{ of size }\le d_n\},$$

so

$$\mathbb E[\kappa(G_{p_0})-1] \le \frac n{d_n+1}+o(n/d_n).$$

Therefore

$$\operatorname{mst}(G_n) \le \mathbb E w(F_0) + \frac{1+p_0}{2}\mathbb E[\kappa(G_{p_0})-1] \le \left(\zeta(3)+\frac12+o(1)\right)\frac n{d_n}.$$

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

$$\operatorname{mst}(G_n) \le \frac{\zeta(3)+1/2+o(1)}{\alpha}.$$

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

$$\frac q2-\frac q{q+1}=\frac{q(q-1)}{2(q+1)}.$$

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

$$\frac{q-1}{2(q+1)}\to\frac12$$

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.