A quadratic upper bound on the Chvátal rank of polytopes in the 0/1-cube
We show that every polytope $P\subseteq[0,1]^n$, and more generally every compact convex set, has Chv\’atal rank at most $12.22n^2+n\log_2 n+2n+4$. This improves the $O(n^2\log n)$ bound of Eisenbrand and Schulz and, together with the $\Omega(n^2)$ lower bound of Rothvo{\ss} and Sanit\`a, shows that the maximum Chv\’atal rank of a polytope in $[0,1]^n$ is $\Theta(n^2)$. More … Read more