New classes of facets of the cut polytope and tightness of Imm22Imm22 Bell inequalities

The Grishukhin inequality is a facet of the cut polytope CUT7□ of the complete graph K7K7, for which no natural generalization to a family of inequalities has previously been found. On the other hand, the Imm22Imm22 Bell inequalities of quantum information theory, found by Collins and Gisin, can be seen as valid inequalities of the cut polytope CUT□(∇Km,m)CUT□(∇Km,m) of the complete tripartite graph ∇Km,m=K1,m,m∇Km,m=K1,m,m. They conjectured that they are facet inducing. We prove their conjecture by relating the Imm22Imm22 inequalities to a new class of facets of CUTN□ that are a natural generalization of the Grishukhin inequality. An important component of the proof is the use of a method called triangular elimination, introduced by Avis, Imai, Ito and Sasaki, for producing facets of CUT□(∇Km,m)CUT□(∇Km,m) from facets of CUTN□.