babylonpolice.com

We study the lift-and-project rank of the stable set polytopes of graphs with
respect to the Lov{\'a}sz--Schrijver SDP operator $\text{LS}_+$, with a
particular focus on a search for relatively small graphs with high
$\text{LS}_+$-rank (the least number of iterations of the $\text{LS}_+$
operator on the fractional stable set polytope to compute the stable set
polytope). In particular, we provide families of graphs whose
$\text{LS}_+$-rank is asymptotically a linear function of its number of
vertices, which is the least possible up to improvements in the constant factor
(previous best result in this direction, from 1999, yielded graphs whose
$\text{LS}_+$-rank only grew with the square root of the number of vertices).
We also provide several new $\text{LS}_+$-minimal graphs, most notably a
$12$-vertex graph with $\text{LS}_+$-rank $4$, and study the properties of a
vertex-stretching operation that appears to be promising in generating
$\text{LS}_+$-minimal graphs.