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 \( \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 \( 4\ell+12 \) vertices with \( \text{LS}_+ \)-rank at least \( \ell \).

Article

Download

View PDF