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

The answer and two follow up questions are below the fold.

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?

Advertisements
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

  1. Nick Read says:

    Please define “diameter”

    • Gil Kalai says:

      Dear Nick, thanks for asking.

      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

  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. Pingback: Elchanan Mossel’s Amazing Dice Paradox (answers to TYI 30) | Combinatorics and more

  6. 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?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s