A simple Introduction to higher order liftings for binary problems


A short, simple, and self-contained proof is presented showing
that $n$-th lifting for the max-cut-polytope is exact.
The proof re-derives the known
observations that the max-cut-polytope is the
projection of a higher-dimensional regular simplex
and that this simplex coincides with the $n$-th semidefinite
lifting. An extension to reduce the dimension
of higher order liftings and to
include linear equality and inequality constraints concludes this paper.