New Classes of Facets of Cut Polytope and Tightness of Imm22 Bell Inequalities

الأصل · EN

The Grishukhin inequality Gr₇ is a facet of CutP₇, the cut polytope on seven points, which is ``sporadic'' in the sense that its proper generalization has not been known. In this paper, we extend Gr₇ to an inequality I(G,H) valid for CutPₙ₊₁ where G and H are graphs with n nodes satisfying certain conditions, and prove a necessary and sufficient condition for I(G,H) to be a facet. This result combined with the triangular elimination theorem of Avis, Imai, Ito and Sasaki settles Collins and Gisin's conjecture in quantum theory affirmatively: the Imm22 Bell inequality is a facet of the correlation polytope CorP(Kₘ,ₘ) of the complete bipartite graph Kₘ,ₘ for all m>=1. We also extend the Gr₈ facet inequality of CutP₈ to an inequality I'(G,H,C) valid for CutPₙ₊₂, and provide a sufficient condition for I'(G,H,C) to be a facet.