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 [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]-rank [Formula: see text] contains [Formula: see text] 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 [Formula: see text] there exists a vertex-transitive graph on at most [Formula: see text] vertices with [Formula: see text]-rank of at least [Formula: see text]. Funding: The research of Levent Tunçel was supported in part by an NSERC Discovery Grant.