## On a representation of the matching polytope via semidefinite liftings

### T. Stephen and L. Tuncel

We consider the relaxation of the matching polytope defined by the non-negativity and
degree constraints. We prove that given an undirected graph on $n$ nodes and the
corresponding relaxation of the matching polytope, $\lfloor \frac{n}{2}\rfloor$ iterations
of the Lov{\'a}sz-Schrijver semidefinite lifting procedure are needed to obtain the
matching polytope, in the worst case. We show that $\lfloor \frac{n}{2}\rfloor$ iterations
of the procedure always suffice.

Research Report 97-11, Department of Combinatorics and Optimization, University of
Waterloo, Waterloo, Ontario, Canada, July 1997.

Contact: ltuncel@math.uwaterloo.ca