## Test your intuition 29: Diameter of various random trees

Both trees in general and random trees in particular are wonderful objects. And there is nothing more appropriate to celebrate Russ Lyons great birthday conference “Elegance in Probability” (taking place now in Tel Aviv) than to test your intuition, dear reader, with questions about probability and trees.

Model 1: consider a set of n vertices {1,2,…,n} and a random spanning tree T on these vertices.

### Test your intuition: What is the behavior of the diameter of T?

The diameter of a graph G is the maximum distance between pairs of vertices of G. The distance between a pair of vertices is the length of the smallest path between them. (For a tree there is a unique path.) Answer for model 1: the diameter of a random tree behaves like $\sqrt n$.

Model 2: assign each edge {i,j} a real number between 0 and 1 uniformly and independently. Let T be the minimum spanning tree.

### Test your intuition: What is the behavior of the diameter of T?

(We refer to the diameter of T regarded as an abstract graph.)

Is the exponent of n larger or smaller than 1/2? What is the exponent?

Model 3: start with an m-gon $C_m$ and add a random diagonal.  Repeat (until you can’t) by adding a new random diagonal as long as it does not cross any previous diagonal and does not use any vertex used by previous diagonals. The dual tree T to the resulting decomposition of $C_m$ has a number of vertices n which is a random variable and is proportional to m.

### Test your intuition: What is the behavior of the diameter of T?

Is the exponent of n larger or smaller than 1/2? What is the exponent?

This entry was posted in Combinatorics, Probability, Test your intuition and tagged , . Bookmark the permalink.

### 19 Responses to Test your intuition 29: Diameter of various random trees

1. Nick Read says:

• Gil Kalai says:

The diameter of a graph G is the maximum distance between pairs of vertices of G. The distance between a pair of vertices is the length of the smallest path between them. (For a tree there is a unique path.) I added the definitions to the post.

2. Nick Read says:

Model 2: n^1/3

• Gil Kalai says:

Nick, what is your intuitive reason for 1/3?

• Nick Read says:

The fact that I wrote a paper on something that seems to be equivalent 🙂

3. Nick Read says:

I guess the fact that it seems to be equivalent is the intuitive part

4. Nick Read says:

See Phys. Rev. E 81, 021130 (2010) and https://arxiv.org/abs/1301.1667 for the rigorous part

5. Vincent says:

Can you elaborate on what ‘random’ means in model 1? Do you pick a spanning tree from the set of all spanning trees with equal probability?

• Gil Kalai says:

Dear Vincent, yes this is what I mean.

6. Julien Berestycki says:

Dear Gil,
The answer from model 2 seems to be in the following paper:
The scaling limit of the minimum spanning tree of the complete graph, by Louigi Addario-Berry, Nicolas Broutin, Christina Goldschmidt and Grégory Miermont, Annals of Probability 45, 5 (2017), pp.3075-3144.

If M_n is the minimum spanning tree of the complete graph with i.i.d. U[0,1] edge-weights, d_n is the graph distance in d_n and \mu_n is the uniform measure on the vertices, then there exists a random binary R-tree (M, d) endowed with a measure \mu such that

(M_n, n^{-1/3} d_n, \mu_n) \to (M, d, \mu)

in distribution as n \to \infty, in the sense of the Gromov–Hausdorff–Prokhorov topology. (M has Minkowski dimension 3 almost surely, and so is not the Brownian CRT.) In particular, this result implies that if D_n is the diameter of M_n then

n^{-1/3} D_n \to D

in distribution as n \to \infty, for some a.s. finite random variable D, which is the diameter of the metric space (M, d).

(In his comment, Nick Read gives a link to Louigi’s paper on the local weak limit of M_n, but that tells us nothing about the convergence of the diameter; I guess he meant to link to the above paper instead.)

7. Nick Read says:

Julien: No, I linked to the paper I intended. That paper and the earlier one by Jackson and myself show that the mass within graph distance n on the random MST on the complete graph or on the Cayley tree or PWIT scales as n^3 when n << N = number of vertices. It is true that this is a local property, unlike the diameter, but my intuition was that the former implies (e.g. by setting n^3=N), that the diameter scales as N^{-1/3}—that is assuming one exponent describes both. It is nice to know that the intuition is correct—and Gil did ask for intuition.

8. Gil Kalai says:

Many thanks for the comments Nick and Julien,

Regarding Model 2 let me also mention the 2006 paper The Diameter of the Minimum Spanning Tree of a Complete Graph by Louigi Addario-Berry, Nicolas Broutin, and Bruce Reed. It gives $n^{1/3}$ settling a 1997 conjecture of Frieze and McDiarmid.

Dear readers, can you guess the exponent in Model 3?

• Nick Read says:

Frieze and McDiarmid 1997 asked: “is [the diameter] $n^{1/2}$?”

• Gil Kalai says:

Dear Nick, I see, so they answered the question in the negative! (A little like this comment . ) Is the paper by Addario-Berry, Broutin, and Reed, the earliest where the exponent 1/3 appeared? Is your paper that you mentioned the one where Newman old prediction is confronted? Is the 1/3 1/2 gap relevant to that conflicting predictions?

• Gil Kalai says:

Here is the arxived version of the paper by Jackson and Read.
Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model

• Nick Read says:
9. Gil Kalai says: