Gap inequalities for the cut polytope (Q1911843)

Let \({n \choose 2}\) denote the set of unordered pairs \(ij\) with \(1 \leq i < j \leq n\) (i.e., \(ij\) and \(ji\) are considered identical). Given a subset \(S \subseteq V = \{1, \dots, n\}\), the set \[ \delta (S) : = \left\{ ij \in {n \choose 2} : \bigl |S \cap \{i,j\} \bigr |= 1 \right\} \] is said to be the cut determined by \(S\). Then the convex hull of the incidence vectors of all cuts is called the cut polytope \(\text{CUT}_n\). The authors introduce a new class of inequalities having a strong connection with the cut polytope \(\text{CUT}_n\). More precisely, these gap inequalities are valid for \(\text{CUT}_n\). Each gap inequality is given by a finite sequence of integers, the ``gap'' being defined as smallest discrepancy arising when decomposing the sequence into two parts that are as equal as possible. Gap inequalities include hypermetric inequalities and negative type inequalities, and they are related to a positive semidefinite relaxation of the max-cut problem, too. The authors present some necessary and sufficient conditions for integer sequences whose corresponding gap inequalities define facets of \(\text{CUT}_n\). They further show that there is no facet defining inequality with gap larger than one and which is induced by a sequence of integers using only two distinct values. Finally, examples are discussed.