  Let X be the set of integer points in some polyhedron. We investigate the
smallest number of facets of any polyhedron whose set of integer points is X.
This quantity, which we call the relaxation complexity of X, corresponds to the
smallest number of linear inequalities of any integer program having X as the
set of feasible solutions that does not use auxiliary variables. We show that
the use of auxiliary variables is essential for constructing polynomial size
integer programming formulations in many relevant cases. In particular, we
provide asymptotically tight exponential lower bounds on the relaxation
complexity of the integer points of several well-known combinatorial polytopes,
including the traveling salesman polytope and the spanning tree polytope.

Combinatorics;Optimization and Control