The twenty-two minimal dichotomy decompositions of the equilateral distance on fiive points.

Bernard Fichet
Laboratoire de Biomathematiques
University of Marseille, France

Given a ¯nite set I with cardinality n, a distance d on I is of L1¡type if (I; d) is isometrically embeddable in some R N endowed with the l1¡norm. It is known that this condition is ful¯lled if and only if d may be written as : d = PJ ®J;dJ; ®J ¸ 0; (J; Jc) cut (or bipartition) of I, where dJ is the di- chotomy associated with J. Geometrically, this formula shows that the set D1 of semi-distances of L1-type is a polyhedral cone. All dichotomy decompositions characterising d as above, form a polytope in the dual space, the vertices of which are the minimal dichotomy decompositions. These minimal elements are strongly connected with some dimensionality problems, generally of very high complexity.

We exhibit here the twenty-two minimal dichotomy decompositions of the distance d1 of the regular simplex for n = 5. A precise investigation of this family allows us to settle a conjecture on the axes de¯ned by an L1-norm principal component analysis of (I; d1), and to recover a result concerning the minimum L1-dimensionality of (I;d1) :