Geometry of cuts and metrics (Q5906765)

For any set \(S\) of \(n\) points, there is a \({n\choose 2}\)-dimensional vector space \(R^E\) generated by the edges (pairs of points) of \(S\). A semimetric is a slight generalization of a metric, allowing distinct points to be at a distance \(0\); these form a convex cone in the positive orthant of \(R^E\), bounded by the hyperplanes defining the various instances of the triangle inequality. A cut is a semantic on a set \(S\) based on a partition \(S= U\cup V\), such that pairs entirely within \(U\) or within \(V\) are at distance \(0\), while pairs intersecting both \(U\) and \(V\) are at distance 1. The cut cone is the set of positive linear combinations of cuts. (For \(n\leq 4\), every semimetric is in the cut cone; for \(n\geq 5\) this is no longer true.) We may also define the cut polytope as the convex hull of the set of cuts. Deza and Laurent show us that cuts and semimetrics turn up in many areas of mathematics. If we think of a single cut as a dichotomous classification of points, the cut cone has natural interpretations in probability theory and statistics. By the same token, a metric is in the cut cone iff it is \(\ell_1\)-embeddable; this yields fruitful connections to many other problems on embedding finite metrics in Banach spaces and leads, in turn, to several chapters on the theory of Delaunay polytopes in lattices. There are also lengthy sections on the application of cuts to graph theory. The final section of the book studies the geometry of the cut cone and polytope themselves. This gets extremely complicated; while the cut cone is defined just by the various instances of the triangle inequality for \(n<5\), there are two distinct types of facet for \(n=5\), three for \(n=6\), and eleven for \(n=7\) (with a total of 38780 facets in the last case!). Perhaps one of the most interesting applications of the geometry of the cut polytope is the construction (Kahn and Kalai, 1993) of a counterexample to Borsuk's long-standing (and widely-believed) conjecture that any set of points in \(R^d\) could be partitioned into \(d+1\) sets of strictly smaller diameter. This is a large and fascinating book. As befits a book which contains material relevant to so many areas of mathematics (and related disciplines such as statistics, physics, computing science, and economics), it is self-contained and written in a readable style. Moreover, the index, bibliography, and table of contents are all that they should be in such a work; it is easy to find as much or as little introductory material as needed.