Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut

We study linear programming relaxations of Vertex Cover and Max Cut arising from repeated applications of the "lift-and-project" method of Lovasz and Schrijver starting from the standard linear programming relaxation. For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that the integrality gap remains at least 2 - epsilon after Omega(epsilon)(log n) rounds, where n is the number of vertices, and Tourlakis proves that integrality gap remains at least 1.5 - epsilon after Omega((log n)(2)) rounds. Fernandez de la Vega and Kenyon prove that the integrality gap of Max Cut is at most 1/2 + epsilon after any constant number of rounds. (Their result also applies to the more powerful Sherali-Adams method.) We prove that the integrality gap of Vertex Cover remains at least 2 - epsilon after Omega(epsilon) (n) rounds, and that the integrality gap of Max Cut remains at most 1/2 + epsilon after Omega(epsilon)(n) rounds.