Supplementary Materials for "Polyhedral Combinatorics of UPGMA Cones"

The material on this page is devoted to the calculations of the spherical volumes of the UPGMA cones. In particular, we provide two mathematica notebooks for computing spherical volumes.

The first notebook uses a simple method to compute spherical volumes. We generate spherically uniformly random points in the positive orthant and apply the UPGMA algorithm to them, recording the number of times a particular chain in the partition lattice arises for trees with a fixed number n of leaves. We ran this code on size n = 4, 5, 6, 7.

To check the computations from the first notebook, we also implemented a variation on the method from the paper (Eickmeyer et al 2007, On the optimality of the neighbor-joining algorithm) using Monte Carlo integration to compute the spherical volume of each cone directly. Stated simply, the spherical volume of a simplical cone can be approximated by taking uniformly random samples from the flat simplex and taking the average value of the Jacobian of the map that takes a point in the flat simplex and maps it to the associated spherical simplex. Hence we must first triangulate our cones into simplicial cones and then compute the volumes of the resulting simplicial cones. After triangulating the cone for a given chain using polymake, we were able to use directly the code from the companion website. That method worked for trees with n=4,5,6 leaves.

For n = 7 leaf trees, it was not possible to compute the triangulation for the cone of a full chain, so we used a combination of the method from (Eickmeyer et al 2007) with the simpler method described above. Namely, we compute a triangulation of a cone associatated to a partial chain, use that to generate random samples, and then apply the UPGMA algorithm to see which chain is produced. For a typical complete chain, we compute the average value of the Jacobian times the indicator function of lying in a particular cone. This method appears in the second mathematica notebook.

In the tables for chains, the first column gives the chain in the partition lattice (minus the bottom 1|2|3|4 and top 1234 elements, which appear in every chain). The second columns gives the number of orbits in the symmetry class. The third column gives the number of rays in the cone. The fourth column is the number of simplices in the triangulation, computed with polymake. The fifth column is the spherical volume of the cone. The sixth column is the fraction of all of the sphere in the positive orthant which is taken up by all chains in the orbit of the given chain.

In the tables for trees, the first column gives the tree. The second column gives the number of trees in that orbit under symmetry. The third column gives the number of cones which make up the UPGMA region for the given tree. The fourth column gives the positions in the tree list of a particular cone appearing in the UPGMA list, together with its multiplicity. The fifth column gives the volume of the UPGMA region, and the sixth column gives the fraction of all of the sphere in the positive orthant which is taken up by all trees in the orbit of the given tree.