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{\'a}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.