Page 31 - Tequio 11
P. 31

On some polytopes in phylogenetics/Hoessly/27-40  29






                Figure 2.
                Two different binary X-trees on the tree T of figure 1.
















                2.2 Polytopes
                Polytopes are seemingly simple geometric objects with flat sides. They appear as convex hulls of a finite set
                of points in Euclidean space (like, e.g., the plane ℝ  or 3-dimensional space ℝ ), and exhibit a rich variety of
                                                           *
                                                                                  A
                combinatorial structures  (Ziegler, 1995). The convex hull of a set of points { - , ⋯ ,  D } ⊂ ℝ  is defined as
                                                                                               /

                                                                  D      D
                                     conv{ - , ⋯ ,  D }: = { ∈ ℝ  ∣   = N  P  P , N  P = 1,  P ≥ 0}
                                                           /
                                                                 PQ-     PQ-

                A polytope is a convex hull of a finite set of points. Well-known examples include two-dimensional polytopes
                that are convex polygons like the square (cf. Figure 3). The dimension of a polytope  is the dimension of the
                smallest Euclidean space which could contain it. As an example, the square of figure [fig_octa] has dimension
                two. A face of a polytope  is any intersection of the polytope with a half-space such that none of the interior
                points of the polytope lie on the boundary of the half-space. Any face of a polytope is a polytope itself. Some
                faces have a special name, faces of dimension  0,1  and  dim() − 1  are called  vertices, edges  and  facets.
                Moreover, the faces of polytopes can be ordered by inclusion, giving the poset of faces. A rougher invariant are
                                     Y
                                Y
                its face numbers  , , … ,  [\](Y) , which are defined as

                                                 = #{ − dimensional faces of }.
                                                 Y
                                                 P

                Putting all the face numbers together gives a convenient way of writing them as the so-called f-vector
                ( , , … ,  Dg- ), where  = dim(). Note that convex polytopes may equivalently be defined as an intersection
                  Y
                       Y
                of a finite number of half-spaces, corresponding to the so-called hyperplane description, see, e.g., (Ziegler,
                1995, §2.4).

                Example 2.2. Consider the d-crosspolytope, which is defined as

                                                j : = conv{ - , − - , ⋯ ,  j , − j } ⊆ ℝ ,
                                                                            j







                                                 Tequio, enero-abril 2021, vol. 4, no. 11
   26   27   28   29   30   31   32   33   34   35   36