Expected Value of the Diameter of a Tree

Modeling Predictive Analytics Decision 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 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 $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 $n ‾\sqrt$ .

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

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.