The Probable Value of the Lovász-Schrijver Relaxations for Maximum Independent Set

Lov{ász and Schrijver [SIAM J. Optim., 1 (1991), pp. 166--190] devised a lift-and-project method that produces a sequence of convex relaxations for the problem of finding in a graph an independent set (or a clique) of maximum size. Each relaxation in the sequence is tighter than the one before it, while the first relaxation is already at least as strong as the Lov{ász theta function [IEEE Trans. Inform. Theory, 25 (1979), pp. 1--7]. We show that on a random graph G_n,1/2, the value of the rth relaxation in the sequence is roughly \rule{0pt}{7pt}$\smash{\sqrt{\rule{0pt}{7pt}\smash{n/2^r}}}$, almost surely. It follows that for those relaxations known to be efficiently computable, namely, for r=O(1), the value of the relaxation is comparable to the theta function. Furthermore, a perfectly tight relaxation is almost surely obtained only at the $r=\Theta(\log n)$ relaxation in the sequence.