The cut cone III: On the role of triangle facets

The cut polytopeP _n is the convex hull of the incidence vectors of the cuts (i.e. complete bipartite subgraphs) of the complete graph onn nodes. A well known class of facets ofP _n arises from the triangle inequalities:x _ij +x _ik +x _jk ≤2 andx _ij −x _ik −x _jk ≤0 for 1≤i, j, k≤n. Hence, the metric polytopeM _n , defined as the solution set of the triangle inequalities, is a relaxation ofP _n .We consider several properties of geometric type forP _n , in particular, concerning its position withinM _n . Strengthening the known fact (3]) thatP _n has diameter 1, we show that any set ofk cuts,k≤log₂ n, satisfying some additional assumption, determines a simplicial face ofMn and thus, also, ofP _n . In particular, the collection of low dimension faces ofP _n is contained in that ofM _n . Among a large subclass of the facets ofP _n , the triangle facets are the closest ones to the barycentrum ofP _n and we conjecture that this result holds in general. The lattice generated by all even cuts (corresponding to bipartitions of the nodes into sets of even cardinality) is characterized and some additional questions on the links between general facets ofP _n and its triangle facets are mentioned.