Random half-integral polytopes
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 … Read more