Expected Value of the Diameter of a Tree

ModelingPredictive AnalyticsDecision Treeposted by Atabey Kaygun November 3, 2017

Description of the problem Gil Kalai asks the following problem: given a random tree on nn vertices asymptotically behaves like nn vertices by generating n=2n=2 to

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: herehereand 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)))))

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

Atabey Kaygun

I do homological and homotopical algebra in the context of noncommutative geometry. You can find a detailed exposition of my past research, my present and future research interests in my research statement. Specifically I am interested in, Hopf equivariant cohomology theories, various flavors of Hochschild (co)homology, cyclic (co)homology and K-Theory. I am also intrested in abstract homotopical algebra, operads, PROPs and their algebras. For the visually inclined, I have a map of my slanted view of the noncommutative geometry landscape.

1