Supplementary Materials for "Polyhedral Combinatorics of UPGMA Cones"

 This webpage contains supplementary material for the paper Polyhedral Combinatorics of UPGMA Cones by Ruth Davidson and Seth Sullivant.  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 the 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.

Simple Spherical Volume Code

Jacobian Numerical Integration Spherical Volume Code

Zipped Files with Triangulations

 All triangulations were computed using polymake. For n = 4,5,6, the files contain triangulations of each symmetry class of cone. For n = 7 the cones for displayed are for partial chains up to a partition with 5 elements. This is necessary because it is not possible to compute a triangulations of cone of a saturated chain in the partition lattice. We then use a MonteCarlo sampling strategy together with an implementation of the UPGMA algorithm to calculate the volumes of the cones.
 n File 4 ZipFour.zip 5 ZipFive.zip 6 ZipSix.zip 7 ZipSeven.zip

Spherical Volume Tables

 The tables below display the results of our spherical volume computations. The both in terms of chains in the partition lattice (i.e. ranked trees) and simply rooted trees. 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.

n = 4

 Chain Orbit Rays Simplices Volume Fraction 1 3|4|12 < 4|123 12 8 3 0.0238 0.5895 2 3|4|12 < 12|34 6 9 5 0.0331 0.4099

 Tree Orbit Cones Multiplicities Volume Fraction 1 (((12)3)4) 12 1 1(1) 0.0238 0.5895 2 ((12)(34)) 3 2 2(2) 0.0662 0.4099

n=5

 Chain Orbit Rays Simplices Volume Fraction 1 3|4|5|12 < 4|5|123 < 5|1234 60 22 48 8.57e-5 0.206 2 3|4|5|12 < 4|5|123 < 123|45 30 24 85 1.07e-4 0.129 3 3|4|5|12 < 5|12|34 < 5|1234 30 29 128 1.73e-4 0.208 4 3|4|5|12 < 5|12|34 < 12|345 30 31 176 1.57e-4 0.189 5 3|4|5|12 < 5|12|34 < 34|125 30 31 204 2.21e-4 0.267

 Tree Orbit Cones Multiplicities Volume Fraction 1 ((((12)3)4)5) 60 1 1(1) 8.57e-5 0.206 2 (((12)3)(45)) 30 3 2(1) 4(1) 5(1) 5.01e-4 0.604 3 (((12)(34))5) 15 2 3(2) 3.14e-4 0.189

n = 6

 Chain Orbit Rays Simplices Volume Fraction 1 3|4|5|6|12 < 4|5|6|123 < 5|6|1234 < 6|12345 360 65 5970 2.05e-8 0.042 2 3|4|5|6|12 < 4|5|6|123 < 5|6|1234 < 1234|56 180 68 10707 2.18e-8 0.022 3 3|4|5|6|12 < 4|5|6|123 < 6|123|45 < 6|12345 180 85 19342 4.24e-8 0.043 4 3|4|5|6|12 < 4|5|6|123 < 6|123|45 < 45|1236 180 88 30014 5.22e-8 0.053 5 3|4|5|6|12 < 4|5|6|123 < 6|123|45 < 123|456 180 89 28333 3.14e-8 0.032 6 3|4|5|6|12 < 5|6|12|34 < 5|6|1234 < 6|12345 180 102 25748 5.26e-8 0.054 7 3|4|5|6|12 < 5|6|12|34 < 5|6|1234 < 1234|56 90 105 44775 5.68e-8 0.029 8 3|4|5|6|12 < 5|6|12|34 < 6|12|345 < 6|12345 180 122 49184 7.17e-8 0.073 9 3|4|5|6|12 < 5|6|12|34 < 6|12|345 < 12|3456| 180 125 60501 4.98e-8 0.051 10 3|4|5|6|12 < 5|6|12|34 < 6|12|345 < 345|126 180 126 85073 8.36e-8 0.085 11 3|4|5|6|12 < 5|6|12|34 < 6|34|125 < 6|12345 180 122 60987 1.01e-7 0.103 12 3|4|5|6|12 < 5|6|12|34 < 6|34|125 < 34|1256 180 125 79760 8.60e-8 0.088 13 3|4|5|6|12 < 5|6|12|34 < 6|34|125 < 125|346 180 126 103937 1.10e-7 0.112 14 3|4|5|6|12 < 5|6|12|34 < 12|34|56 < 12|3456 90 153 158634 1.04e-7 0.053 15 3|4|5|6|12 < 5|6|12|34 < 12|34|56 < 34|1256 90 153 167870 1.27e-7 0.065 16 3|4|5|6|12 < 5|6|12|34 < 12|34|56 < 56|1234 90 152 186418 1.65e-7 0.084

 Tree Orbit Cones Multiplicities Volume Fraction 1 (((((12)3)4)5)6) 360 1 1(1) 2.05e-8 0.042 2 ((((12)3)4)(56)) 180 4 2(1) 4(1) 9(1) 13(1) 2.10e-7 0.216 3 ((((12)3)(45))6) 180 3 3(1) 8(1) 11(1) 2.16e-7 0.223 4 (((12)3)((45)6)) 90 6 5(2) 10(2) 13(2) 4.50e-7 0.229 5 ((((12)(34))5)6) 90 2 6(2) 1.05e-7 0.054 6 (((12)(34))(56)) 45 8 7(2) 14(2) 15(2) 16(2) 9.06e-7 0.231

n = 7

 Tree Chain Orbit Volume Fraction 1 1 3|4|5|6|7|12 < 4|5|6|7|123 < 5|6|7|1234 < 6|7|12345 < 7|123456 2520 2.75e-13 0.0049744 2 2 3|4|5|6|7|12 < 4|5|6|7|123 < 5|6|7|1234 < 6|7|12345 < 12345|67 1260 2.51e-13 0.0022673 3 3 3|4|5|6|7|12 < 4|5|6|7|123 < 5|6|7|1234 < 7|1234|56 < 7|123456 1260 5.03e-13 0.0045417 4 2 3|4|5|6|7|12 < 4|5|6|7|123 < 5|6|7|1234 < 7|1234|56 < 56|12347 1260 6.05e-13 0.005459 5 4 3|4|5|6|7|12 < 4|5|6|7|123 < 5|6|7|1234 < 7|1234|56 < 1234|567 1260 2.98e-13 0.0026894 6 5 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 6|7|12345 < 7|123456 1260 8.07e-13 0.0072787 7 6 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 6|7|12345 < 12345|67 630 7.67e-13 0.0034593 8 3 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|45|1236 < 7|123456 1260 1.52e-12 0.0137008 9 2 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|45|1236 < 45|12367 1260 1.26e-12 0.011364 10 4 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|45|1236 < 1236|457 1260 1.34e-12 0.0120465 11 7 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|123|456 < 7|123456 1260 1.06e-12 0.0095354 12 4 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|123|456 < 123|4567 1260 5.52e-13 0.0049807 13 4 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 7|123|456 < 456|1237 1260 1.18e-12 0.0106398 14 6 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 123|45|67 < 45|12367 630 1.89e-12 0.0085127 15 6 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 123|45|67 < 67|12345 630 2.40e-12 0.0108365 16 8 3|4|5|6|7|12 < 4|5|6|7|123 < 6|7|123|45 < 123|45|67 < 123|4567 630 1.18e-12 0.0053149 17 9 3|4|5|6|7|12 < 5|6|7|12|34 < 5|6|7|1234 < 6|7|12345 < 7|123456 1260 8.64e-13 0.0077927 18 10 3|4|5|6|7|12 < 5|6|7|12|34 < 5|6|7|1234 < 6|7|12345 < 12345|67 630 7.71e-13 0.0034796 19 11 3|4|5|6|7|12 < 5|6|7|12|34 < 5|6|7|1234 < 7|1234|56 < 7|123456 630 1.57e-12 0.0071016 20 10 3|4|5|6|7|12 < 5|6|7|12|34 < 5|6|7|1234 < 7|1234|56 < 56|12347 630 1.90e-12 0.0085622 21 8 3|4|5|6|7|12 < 5|6|7|12|34 < 5|6|7|1234 < 7|1234|56 < 1234|567 630 9.12e-13 0.0041119 22 5 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 6|7|12345 < 7|123456 1260 1.50e-12 0.0135731 23 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 6|7|12345 < 12345|67 630 1.42e-12 0.0064276 24 3 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|12|3456 < 7|123456 1260 1.57e-12 0.0141924 25 2 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|12|3456 < 12|34567 1260 9.07e-13 0.0081846 26 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|12|3456 < 3456|127 1260 1.54e-12 0.0138995 27 7 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|345|126 < 7|123456 1260 3.14e-12 0.0283524 28 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|345|126 < 126|3457 1260 2.98e-12 0.0268784 29 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 7|345|126 < 345|1267 1260 2.20e-12 0.0198035 30 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 12|345|67 < 12|34567 630 2.06e-12 0.0092775 31 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 12|345|67 < 67|12345 630 3.88e-12 0.0174857 32 8 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|12|345 < 12|345|67 < 345|1267 630 2.53e-12 0.011412 33 5 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 6|7|12345 < 7|123456 1260 2.14e-12 0.0193047 34 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 6|7|12345 < 12345|67 630 2.02e-12 0.0091143 35 3 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|34|1256 < 7|123456 1260 2.73e-12 0.0245906 36 2 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|34|1256 < 34|12567 1260 1.79e-12 0.0161872 37 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|34|1256 < 1256|347 1260 2.62e-12 0.0236879 38 7 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|125|346 < 7|123456 1260 4.08e-12 0.0367775 39 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|125|346 < 125|3467 1260 2.64e-12 0.0237894 40 4 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 7|125|346 < 346|1257 1260 4.19e-12 0.0377749 41 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 34|125|67 < 34|12567 630 3.75e-12 0.0169126 42 6 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 34|125|67 < 67|12345 630 5.90e-12 0.0265927 43 8 3|4|5|6|7|12 < 5|6|7|12|34 < 6|7|34|125 < 34|125|67 < 125|3467 630 3.64e-12 0.0164409 44 11 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|12|3456 < 7|123456 630 4.00e-12 0.0180277 45 10 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|12|3456 < 12|34567 630 2.34e-12 0.0105574 46 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|12|3456 < 3456|127 630 4.00e-12 0.0180387 47 11 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|34|1256 < 7|123456 630 4.81e-12 0.0217117 48 10 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|34|1256 < 34|12567 630 3.18e-12 0.0143589 49 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|34|1256 < 1256|347 630 4.82e-12 0.0217402 50 11 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|56|1234 < 7|123456 630 6.30e-12 0.0284111 51 10 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|56|1234 < 56|12347 630 4.96e-12 0.0223498 52 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 7|56|1234 < 1234|567 630 5.63e-12 0.0254009 53 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|34|567 < 12|34567 630 3.49e-12 0.0157426 54 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|34|567 < 34|12567 630 3.97e-12 0.0178949 55 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|34|567 < 567|1234 630 5.78e-12 0.0260501 56 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|56|347 < 12|34567 630 4.88e-12 0.021997 57 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|56|347 < 56|12347 630 6.53e-12 0.0294707 58 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 12|56|347 < 347|1256 630 8.01e-12 0.0361477 59 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 34|56|127 < 34|12567 630 6.56e-12 0.0295797 60 6 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 34|56|127 < 56|12347 630 7.72e-12 0.034846 61 8 3|4|5|6|7|12 < 5|6|7|12|34 < 7|12|34|56 < 34|56|127 < 127|3456 630 8.51e-12 0.0383664

 Tree Orbit Cones Multiplicities Volume Fraction 1 ((((((12)3)4)5)6)7) 2520 1 1(1) 2.75e-13 0.0049744 2 (((((12)3)4)5)(67)) 1260 5 2(1) 4(1) 9(1) 25(1) 36(1) 4.82e-12 0.0434621 3 (((((12)3)4)(56))7) 1260 4 3(1) 8(1) 24(1) 35(1) 6.32e-12 0.0570255 4 ((((12)3)4)((56)7)) 1260 10 5(1) 10(1) 12(1) 13(1) 26(1) 28(1) 29(1) 37(1) 39(1) 40(1) 1.95e-11 0.1761900 5 (((((12)3)(45))6)7) 1260 3 6(1) 22(1) 33(1) 4.45e-12 0.0401565 6 ((((12)3)(45))(67)) 630 15 7(1) 14(1) 15(1) 23(1) 30(1) 31(1) 34(1) 41(1) 42(1) 53(1) 54(1) 56(1) 57(1) 59(1) 60(1) 5.72e-11 0.2581498 7 ((((12)3)((45)6))7) 630 6 11(2) 27(2) 38(2) 1.66e-11 0.0746653 8 (((12)3)((45)(67))) 315 20 16(2) 21(2) 32(2) 43(2) 46(2) 49(2) 52(2) 55(2) 58(2) 61(2) 9.00e-11 0.2030237 9 (((((12)(34))5)6)7) 630 2 17(2) 1.73e-12 0.0077927 10 ((((12)(34))5)(67)) 315 10 18(2) 20(2) 45(2) 48(2) 51(2) 2.63e-11 0.0593079 11 ((((12)(34))(56))7) 315 8 19(2) 44(2) 47(2) 50(2) 3.33e-11 0.0752521