We show that half-integral polytopes obtained as the convex hull of a random set of half-integral points of the 0/1 cube have rank as high as Ω(logn/loglogn) with positive probability — even if the size of the set relative to the total number of half-integral points of the cube tends to 0. The high rank is due to certain obstructions. We determine the exact threshold number, when these obstructions cease to exist.

## Article

Download

View Random half-integral polytopes