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 [Formula: see text] applied to the fractional stable set polytope. In particular, we show that for every positive integer [Formula: see text], the smallest possible graph with [Formula: see text]-ra...