Facets for the cut cone II: Clique-web inequalities

The authors study new classes of facets for the cut cone Cn generated by the cuts of the complete graph on n vertices. This cone can also be interpreted as the cone of all semi-metrics on n points that are isometrically l1-embeddable and, in fact, the study of the facets of the cut polytope is in some sense equivalent to the study of the facets of Cn. These new facets belong to the class of clique-web inequalities which generalize the hypermetric and cycle inequalities as well as the bicycle odd wheel inequalities.