Stable Set Polytopes with Rank $|V(G)|/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 $\mathcal{\ell }$, the smallest possible graph with ${\text{LS}}_{+}$-rank $\mathcal{\ell }$ contains $3\mathcal{\ell }$ vertices. This result is sharp and settles a conjecture posed by Lipták and Tunçel [27] in 2003 as well as answers a generalization of a problem posed by Knuth [21] in 1994. We also show that for every positive integer $\mathcal{\ell }$ there exists a vertex-transitive graph on at most $4\mathcal{\ell }+12$ vertices with ${\text{LS}}_{+}$-rank of at least $\mathcal{\ell }$.

Funding: The research of Levent Tunçel was supported in part by an NSERC Discovery Grant.