## 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.

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

• 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.

Model 2: n^1/3

• Gil Kalai says:

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

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

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

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.