THE INEQUICUT CONE

Given a complete graph K(n) on n nodes and a subset S of nodes, the cut delta(S) defined by S is the set of edges of K(n) with exactly one endnode in S. A cut delta(S) is an equicut if absolute value of S = [n/2] or [n/2] and an inequicut, otherwise. The cut cone C(n) (or inequicut cone IC(n)) is the cone generated by the incidence vectors of all cuts (or inequicuts) of K(n). The equicut polytope EP(n), studied by Conforti et al. (1990), is the convex hull of the incidence vectors of all equicuts. We prove that IC(n) and EP(n) 'inherit' all facets of the cut cone C(n), namely, that every facet of the cut cone C(n) yields (by zero-lifting) a facet of the inequicut cone IC(m) for n < [m/2] and of EP(m) for m odd, m greater-than-or-equal-to 2n + 1. We construct several new classes of facets, not arising from C(n), for the inequicut cone IC(n) and we describe its facial structure for n less-than-or-equal-to 7.