Description of the problem
According to Kalai, the expected value of the diameter of a random tree on n vertices asymptotically behaves like 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)))
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 n3/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))))
Here is a graph of the results for n=2 to n=60.