  Stabbing Planes (also known as Branch and Cut) is a proof system introduced
very recently which, informally speaking, extends the DPLL method by branching
on integer linear inequalities instead of single variables. The techniques
known so far to prove size and depth lower bounds for Stabbing Planes are
generalizations of those used for the Cutting Planes proof system. For size
lower bounds these are established by monotone circuit arguments, while for
depth these are found via communication complexity and protection. As such
these bounds apply for lifted versions of combinatorial statements. Rank lower
bounds for Cutting Planes are also obtained by geometric arguments called
protection lemmas.
  In this work we introduce two new geometric approaches to prove size/depth
lower bounds in Stabbing Planes working for any formula: (1) the antichain
method, relying on Sperner's Theorem and (2) the covering method which uses
results on essential coverings of the boolean cube by linear polynomials, which
in turn relies on Alon's combinatorial Nullenstellensatz.
  We demonstrate their use on classes of combinatorial principles such as the
Pigeonhole principle, the Tseitin contradictions and the Linear Ordering
Principle. By the first method we prove almost linear size lower bounds and
optimal logarithmic depth lower bounds for the Pigeonhole principle and
analogous lower bounds for the Tseitin contradictions over the complete graph
and for the Linear Ordering Principle. By the covering method we obtain a
superlinear size lower bound and a logarithmic depth lower bound for Stabbing
Planes proof of Tseitin contradictions over a grid graph.
