Sherali-Adams and the binary encoding of combinatorial principles

Stefan Dantchev, Abdul Ghani, Barnaby Martin

We consider the Sherali-Adams (SA) refutation system together with the unusual binary encoding of certain combinatorial principles. For the unary encoding of the Pigeonhole Princip…