Tight rank lower bounds for the Sherali-Adams proof system

We consider a proof (more accurately, refutation) system based on the Sherali-Adams (SA) operator associated with integer linear programming. If F is a CNF contradiction that admits a Resolution refutation of width k and size s. then we prove that the SA rank of F is <= k and the SA size of F is <= (k + 1)s + 1. We establish that the SA rank of both the Pigeonhole Principle PHPn-1n and the Least Number Principle LNPn is n - 2. Since the SA refutation system rank-simulates the refutation system of Lovasz-Schrijver without semidefinite cuts (LS), we obtain as a corollary linear rank lower bounds for both of these principles in LS. (C) 2009 Published by Elsevier B.V.