Stable Set Polytopes with Rank $\mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}3$ for the Lovász--Schrijver SDP Operator

We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász–Schrijver SDP operator ${\text{LS}}_{+}$ applied to the fractional stable set polytope. In particular, we show that for every positive integer $\mathrm{\ell }$, the smallest possible graph with ${\text{LS}}_{+}$-rank $\mathrm{\ell }$ contains $3\mathrm{\ell }$ vertices. This result is sharp and settles a conjecture posed by Lipták and the second author in 2003, as well as answers a generalization of a problem posed by Knuth in 1994. We also show that for every positive integer $\mathrm{\ell }$ there exists a vertex-transitive graph on at most $4\mathrm{\ell }+12$ vertices with ${\text{LS}}_{+}$-rank at least $\mathrm{\ell }$.