On defining sets of vertices of the hypercube by linear inequalities

This paper shows that for any subset S of vertices of the n-dimensional hypercube, ind(S)≤2^n?1, where ind(S) is the minimum number of linear inequalities needed to define S. Furthermore, for any k in the range 1≤k≤2^n?1, there is an S with ind(S) = k, with the defining inequalities taken as canonical cuts. Other related results are included, and all are proven by explicit constructions of the sets S or explicit definitions of such sets by linear inequalities.The paper is aimed at researchers in bivalent programming, since it provides upper bounds on the performance of algorithms which combine several linear constraints into one, even when the given constraints have a particularly simple form.