Those Ubiquitous Cut Polyhedra

I first met Paul Erdos on August 3, 1975 in the Stanford apartment of my Ph.D. supervisor, Vasek Chvatal. Erdos asked me what he asked everyone: “What are you working on?” I was working on two topics involving finite metrics, which I knew was one of Erdos’ favourite subjects. I started by defining what I called the Hamming cone, and is now known as the cut cone, CUTn. This is the conic hull of the 0/1 edge incidence vectors of the 2n−1 cuts in the complete graph Kn. The edge incidence vectors corresponding to a cut have the form x = (xij : 1 ≤ i < j ≤ n), where xij = 1 if and only if vertices i and j are on different sides of the cut. I proceeded to explain what seemed like a rather esoteric conjecture of Michel Deza on the form of the facets of the cut cone. The second topic was about determining the extreme rays of the metric cone, METn. This cone is the set of solutions x = (xij : 1 ≤ i < j ≤ n) to the triangle inequalities: xik ≤ xij + xjk, 1 ≤ i, j, k ≤ n, where the i, j, k are distinct, and we identify xij with xji. These solutions are often called finite semi-metrics. The cut vectors, which generate CUTn, are also extreme rays of METn. An encyclopedic treatment of these polyhedra is contained in the book by Michel Deza and Monique Laurent [2]. Erdos listened politely but I suspected that he was wondering why I was interested in these two questions. Later, in 1977, at my Ph.D. defence in the now defunct Department of Operations Research, I was asked what what was the connection between the two topics of my thesis. I did not have the answer until later. In 1979, during my first trip to Japan, I met Masao Iri. He explained to me what is often called the “Japanese theorem”[3]: a generalization of Ford and Fulkerson’s max flow/min cut theorem, which is a condition based on the cut cone, to fractional multicommodity flows, where the condition is based on the metric cone. So here was a first connection and application. Around the same time as Iri’s work, physicists had been asking similar questions to Deza’s in terms of what they called the Slater hull, which is isomorphic to the cut cone (eg., see [4]). This was a second application. ∗School of Informatics, Kyoto University and School of Computer Science, McGill University, avis@cs.mcgill.ca After relating this to Ron Graham, he remarked that it was impossible to escape from one’s Ph.D. thesis. Indeed, with remarkable regularity I come across yet another application of these and related polyhedra. In this talk I will outline a few of my favourites, some old and some new, as time allows: • Given a set of pairwise distances between n points, can you locate the points in space so that the L1 distance between each pair of points matches its given distance? • Consider five properties that a man may have: tall, handsome, rich, strong, intelligent. It is quite possible to have a population of males so that two thirds of them are either tall or handsome, but not both. The same is true for any other pair of properties. But it is not possible that this can simultaneously hold for every pair of the five properties. (It can hold for any pair of four properties.) • Two well separated physics labs perform measurements on some quantum system and later compute correlations between their results. Could the same set of correlations have been obtained by simply sampling coloured balls from two urns? • An open pit mining company has core samples of blocks in the ground. Can they achieve a profit of $K by mining at most M tons of material? I am not sure if any of this would have interested Erdos, but I am sure he enjoyed the irony of it helping my computer mutt earn an Erdos number of two [1].

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.