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 and the Least Number Principle is n−2. Since the SA refutation system rank-simulates the refutation system of Lovász–Schrijver without semidefinite cuts (LS), we obtain as a corollary linear rank lower bounds for both of these principles in LS.