# Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator

 We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator $$\text{LS}_+$$, with a particular focus on a search for relatively small graphs with high $$\text{LS}_+$$-rank (the least number of iterations of the $$\text{LS}_+$$ operator on the fractional stable set polytope to compute the stable set polytope). In particular, we provide families of graphs whose $$\text{LS}_+$$-rank is asymptotically a linear function of its number of vertices, which is the least possible up to improvements in the constant factor (previous best result in this direction, from 1999, yielded graphs whose $$\text{LS}_+$$-rank only grew with the square root of the number of vertices). We also provide several new $$\text{LS}_+$$-minimal graphs, most notably a 12-vertex graph with $$\text{LS}_+$$-rank 4, and study the properties of a vertex-stretching operation that appears to be promising in generating $$\text{LS}_+$$-minimal graphs.