Expected Value of the Diameter of a Tree

Description of the problem

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

According to Kalai, the expected value of the diameter of a random tree on \(n\) vertices asymptotically behaves like \(\sqrt{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, here and 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 \(n\) vertices by generating \(n^{3/2}\) such 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=2\) to \(n=60\).