# Expected Value of the Diameter of a Tree

ModelingPredictive AnalyticsDecision Treeposted by Atabey Kaygun November 3, 2017 Atabey Kaygun

## Description of the problem

Gil Kalai asks the following problem: given a random tree on nn vertices, what is the expected value of its diameter?

According to Kalai, the expected value of the diameter of a random tree on nn vertices asymptotically behaves like n‾√n.

We can certainly devise an experiment to see that this is the case.

## Random trees and diameter

I have talked about uniformly generating random trees and measuring diameters of graphs before: here, hereand here. So, let us put them to use for this problem. As before, I will use a list of two vertices to denote an edge, and a list of such edges to denote a graph.

First, I need a function to generate uniformly random trees

```
(defun random-tree (n)
(loop for i from 1 below n
collect (list (random i) i)))
```

`RANDOM-TREE`

and three other functions to measure the diameter

```
(defun vertices (G)
(remove-duplicates (reduce #'union G)))
(defun eccentricity (x G)
(let* ((A (vertices G))
(size (length A))
(nbhd (let ((H (remove-duplicates
(union G (mapcar #'reverse G))
:test #'equal))
(res nil))
(dolist (edge H res)
(if (assoc (car edge) res)
(push (cadr edge) (cdr (assoc (car edge) res)))
(push (copy-list edge) res))))))
(labels ((vicinity (u) (assoc u nbhd)))
(do ((n 0 (1+ n))
(V A (set-difference V W))
(W (vicinity x)
(intersection V (reduce #'append (mapcar #'vicinity W)))))
((or (null V) (> n size)) n)))))
(defun diameter-radius (G)
(let ((bag (loop for v in (vertices G) collect (eccentricity v G))))
(cons (reduce #'max bag) (reduce #'min bag))))
```

```
VERTICES
ECCENTRICITY
DIAMETER-RADIUS
```

Here is a function to measure the expected value of diameter of a random tree on nn vertices by generating n3/2n3/2such graphs and measuring the average diameter.

```
(defun test (n)
(let* ((m (floor (expt n 1.5)))
(bag (loop repeat m collect (diameter-radius (random-tree n)))))
(cons (/ (reduce #'+ (mapcar #'car bag)) m)
(/ (reduce #'+ (mapcar #'cdr bag)) m))))
```

`TEST`

Here is a graph of the results for n=2n=2 to n=60n=60.

Original Source.