Stable Set Polytopes with Rank $|V(G)|/3$ for the Lovász--Schrijver SDP Operator
For researchers in combinatorial optimization and semidefinite programming, this resolves a long-standing open problem about the exact size of graphs achieving a given LS_+ rank.
The authors prove that the smallest graph with Lovász–Schrijver SDP rank ℓ has exactly 3ℓ vertices, settling a 2003 conjecture, and construct vertex-transitive graphs with rank at least ℓ on at most 4ℓ+12 vertices.
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$.