Rank of random half-integral polytopes — extended abstract —

We will show that random half-integral polytopes contain certain sets Fk with high probability, the sets of k-tuples with entries in , and exactly one entry equal to . We precisely determine the threshold number k for which the phase transition occurs. Using these random polytopes we show that establishing integer-infeasibility takes rounds of (almost) any cutting-plane procedure with high probability whenever the number of vertices is θ(n3). As a corollary, a relationship between the number of vertices and the rank of the polytope with respect to (almost) any cutting-plane procedure follows.