A note on random minimum length spanning trees

Alan Frieze^{∗}  Miklós Ruszinkó^{†}

Lubos Thoma^{‡} Department of Mathematical Sciences Carnegie Mellon University Pittsburgh PA15213, USA

                            alan@random.math.cmu.edu,
                            ruszinko@lutra.sztaki.hu,
                             thoma@qwes.math.cmu.edu

Submitted June 28, 2000, Accepted August 11, 2000

Abstract Consider a connected r-regular n-vertex graph G with random independent edge lengths, each uniformly distributed on [0, 1]. Let mst(G) be the expected length of a minimum spanning tree. We show in this paper that if G is sufficiently highly edge connected then the expected length of a minimum spanning tree is ∼ \frac{n}{r}ζ(3). If we omit the edge connectivity condition, then it is at most ∼ \frac{n}{r}(ζ(3) + 1).

1 Introduction

Given a connected simple graph G = (V, E) with edge lengths x = (x_{e} : e ∈ E), let mst(G, x) denote the minimum length of a spanning tree. When X = (X_{e} : e ∈ E) is a family of independent random variables, each uniformly distributed on the interval [0, 1], denote the expected value E(mst(G, X)) by mst(G). Consider the complete graph K_{n}. It is known (see [2]) that, as n → ∞, mst(K_{n}) → ζ(3) . Here ζ(3) = ∑_{j=1}^{∞} j^{−3} ∼ 1.202. Beveridge, Frieze and McDiarmid [1] proved two theorems that together generalise the previous results of [2], [3], [5].

∗Supported in part by NSF Grant CCR9818411 email: alan@random.math.cmu.edu

†Permanent Address Computer and Automation Research Institute of the Hungarian Academy of Sciences, Budapest, P.O.Box 63, Hungary-1518. Supported in part by OTKA Grants T 030059 and T 29074 FKFP 0607/1999. email: ruszinko@lutra.sztaki.hu

‡Supported in part by NSF grant DMS-9970622. email: thoma@qwes.math.cmu.edu

Theorem 1 For any n-vertex connected graph G,

mst(G) ≥ \frac{n}{Δ}(ζ(3) − ϵ_{1})

where Δ = Δ(G) denotes the maximum degree in G and ϵ_{1} = ϵ_{1}(Δ) → 0 as Δ → ∞.

For an upper bound we need expansion properties of G.

Theorem 2 Let α = α(r) = O(r^{−1/3}) and let ρ = ρ(r) and ω = ω(r) tend to infinity with r. Suppose that the graph G = (V, E) is connected and satisfies

r ≤ δ ≤ Δ ≤ (1 + α)r,  (1)

where δ = δ(G) denotes the minimum degree in G. Suppose also that

|(S : S̄)|/|S| ≥ ωr^{2/3} log r for all S ⊆ V with r/2 < |S| ≤ min{ρr, |V |/2},  (2)

where (S : S̄) = {(x, y) ∈ E : x ∈ S, y ∈ S̄ = E \ S}. Then

|mst(G) − \frac{n}{r}ζ(3)| ≤ ϵ_{2} \frac{n}{r}

where the ϵ_{2} = ϵ_{2}(r) → 0 as r → ∞.

For regular graphs we of course take α = 0.

The expansion condition in the above theorem is probably not the “right one” for obtaining mst(G) ∼ \frac{n}{r}ζ(3). We conjecture that high edge connectivity is sufficient: Let λ = λ(G) denote the edge connectivity of G.

Conjecture 1 Suppose that (1) holds. Then,

|mst(G) − \frac{n}{r}ζ(3)| ≤ ϵ_{3} \frac{n}{r}

where ϵ_{3} = ϵ_{3}(λ) → 0 as λ → ∞.

Note that λ → ∞ implies r → ∞.

Along these lines, we prove the following theorem.

Theorem 3 Assume α = α(r) = O(r^{−1/3}) and (1) is satisfied. Suppose that r ≥ λ(G) ≥ ωr^{2/3} log n where ω = ω(r) tends to infinity with r. Then

|mst(G) − \frac{n}{r}ζ(3)| ≤ ϵ_{4} \frac{n}{r}

where the ϵ_{4} = ϵ_{4}(r) → 0 as r → ∞.

Remark: It is worth pointing out that it is not enough to have r → ∞ in order to have the result of Theorem 2, that is, we need some extra condition such as high edge connectivity. For consider the graph Γ(n, r) obtained from n/r r-cliques C_{1}, C_{2}, …, C_{n/r} by deleting an edge (x_{i}, y_{i}) from C_{i}, 1 ≤ i ≤ n/r then joining the cliques into a cycle of cliques by adding edges (y_{i}, x_{i+1}) for 1 ≤ i ≤ n/r. It is not hard to see that

mst(Γ(n, r)) ∼ \frac{n}{r} (ζ(3) + \frac{1}{2})

if r → ∞ with r = o(n). We repeat the conjecture from [1] that this is the worst-case, i.e.

Conjecture 2 Assuming only the conditions of Theorem 1,

mst(G) ≤ \frac{n}{δ} (ζ(3) + \frac{1}{2} + ϵ_{5})

where ϵ_{5} = ϵ_{5}(δ) → 0 as δ → ∞.

We prove instead

Theorem 4 If G is a connected graph then

mst(G) ≤ \frac{n}{δ}(ζ(3) + 1 + ϵ_{6})

where the ϵ_{6} = ϵ_{6}(δ) → 0 as δ → ∞.

We finally note that high connectivity is not necessary to obtain the result of Theorem 2. Since if r = o(n) then one can tolerate a few small cuts. For example, let G be a graph which satisfies the conditions of Theorem 2 and suppose r = o(n). Then taking 2 disjoint copies of G and adding a single edge joining them we obtain a graph G′ for which mst(G′) ∼ \frac{1}{2} + \frac{n′}{r} ζ(3) ∼ \frac{n′}{r} ζ(3) where n′ = 2n is the number of vertices of G′.

2 Proof of Theorem 3

Given a connected graph G = (V, E) with |V | = n and 0 ≤ p ≤ 1, let G_{p} be the random subgraph of G with the same vertex set which contains those edges e with X_{e} ≤ p. Let κ(G) denote the number of components of G. We shall first give a rather precise description of mst(G).

Lemma 1 [1] For any connected graph G,

mst(G) = ∫_{p=0}^{1} E(κ(G_{p}))dp − 1.  (3)

□

We substitute p = x/r in (3) to obtain

mst(G) = \frac{1}{r} ∫_{x=0}^{r} E(κ(G_{x/r}))dx − 1.

Now let C_{k,x} denote the total number of components in G_{x/r} with k vertices. Thus

mst(G) = \frac{1}{r} ∫_{x=0}^{r} ∑_{k=1}^{n} E(C_{k,x})dx − 1.  (4)

Proof of Theorem 3

In order to use (4) we need to consider three separate ranges for x and k, two of which are satisfactorily dealt with in [1]. Let A = (r/ω)^{1/3}, B = ⌊(Ar)^{1/4}⌋ so that each of Bα, AB^{2}/r and A/B → 0 as r → ∞. These latter conditions are needed for the analysis of the first two ranges. Range 1: 0 ≤ x ≤ A and 1 ≤ k ≤ B – see [1].

\frac{1}{r} ∫_{x=0}^{A} ∑_{k=1}^{B} E(C_{k,x})dx ≤ (1 + o(1))\frac{n}{r}ζ(3).

Range 2: 0 ≤ x ≤ A and k > B – see [1].

\frac{1}{r} ∫_{x=0}^{A} ∑_{k=B}^{n} E(C_{k,x})dx = o(n/r).

Range 3: x ≥ A.

We use a result of Karger [4]. A cut (S : S̄) = {(u, v) ∈ E : u ∈ S, v ∉ S} of G is γ-minimal if |(S : S̄)| ≤ γλ. Karger proved that the number of γ-minimal cuts is O(n^{2γ}). We can associate each component of G_{p} with a cut of G. Thus

∑_{k=1}^{n} E(C_{k,x}) ≤ O (∑_{s=λ}^{∞} n^{2s/λ} (1 − \frac{x}{r})^{s}) = O (∑_{s=λ}^{∞}(n^{2r/λ}e^{−x})^{s/r})

= O (∫_{s=λ}^{∞}(n^{2r/λ}e^{−x})^{s/r}ds) = O (\frac{rn^{2}e^{−xλ/r}}{x − \frac{2r}{λ} log n}) ,

and using Aλ ≥ ω^{2/3}r log n we obtain

\frac{1}{r} ∫_{x=A}^{r} ∑_{k=1}^{n} E(C_{k,x})dx = O (∫_{x=A}^{r} \frac{n^{2}e^{−xλ/r}}{x − \frac{2r}{λ} log n}dx)

= O (A^{−1} ∫_{x=A}^{r} n^{2}e^{−xλ/r}dx) = O (\frac{rn^{2}}{Aλ} e^{−Aλ/r}) = o(n/r).

We complete the proof by applying Lemma 1. □

3 Proof of Theorem 4

We keep the definitions of A, B and Ranges 1,2, but we split Range 3 and let δ = r. Range 3a: x ≥ A and k ≤ (1 − ϵ)r, 0 < ϵ < 1, arbitrary – see [1] (here ϵ = 1/2 but the argument works for arbitrary ϵ).

\frac{1}{r} ∫_{x=A}^{r} ∑_{k=1}^{(1−ϵ)r} E(C_{k,x})dx = o(n/r).

Range 3b: x ≥ A and k > (1 − ϵ)r.

Clearly

∑_{k=(1−ϵ)r}^{n} C_{k,x} ≤ \frac{n}{(1 − ϵ)r}

and hence

\frac{1}{r} ∫_{x=A}^{r} ∑_{k=(1−ϵ)r}^{n} E(C_{k,x})dx ≤ \frac{n}{(1 − ϵ)r}.

We again complete the proof by applying Lemma 1. □

References

[1] A. Beveridge, A. M. Frieze and C. J. H. McDiarmid, Minimum length spanning trees in regular graphs, Combinatorica 18 (1998) 311-333.

[2] A. M. Frieze, On the value of a random minimum spanning tree problem, Discrete Applied Mathematics 10 (1985) 47 - 56.

[3] A. M. Frieze and C. J. H. McDiarmid, On random minimum length spanning trees, Combinatorica 9 (1989) 363 - 374.

[4] D. R. Karger, A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability Problem, Proceedings of the twenty-seventh annual ACM Symposium on Theory of Computing (1995) 11-17.

[5] M. Penrose, Random minimum spanning tree and percolation on the n-cube, Random Structures and Algorithms 12 (1998) 63 - 82.