Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator

Abstract

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 $\ell$, the smallest possible graph with ${\text{LS}}_{+}$-rank $\ell$ contains $3\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 $\ell$ there exists a vertex-transitive graph on at most $4\ell +12$ vertices with ${\text{LS}}_{+}$-rank at least $\ell$.