The Lasserre Rank of the Cropped Hypercube

Abstract

In an $n$-dimensional \emph{cropped hypercube} each of the $2^n$ cropping inequalities chops off a single corner of the $0$--$1$ hypercube by an ${\ell }_1$-distance $\rho$. The case $\rho =1/2$ has been extensively studied in the literature. This paper shows that the Lasserre rank of the $n$-dimensional cropped hypercube where $\rho =1/2$, $n\ge 2$, is the smallest integer $0\le t\le n$ such that ${\Delta }_t<0$ in the recurrence ${\Delta }_{-1}=1$, ${\Delta }_0=n-1$, ${\Delta }_t=(n-1){\Delta }_{t-1}-t(n-t+1){\Delta }_{t-2}$. It follows that the Lasserre rank can be computed in time $O(n^2{\log }^{2}n)$. Asymptotically, the rank is $\frac{n}{2}+c_{1/2}\sqrt{n}+o(\sqrt{n})$, where $c_{1/2}$ is the unique zero of a given function. Numerically, $c_{1/2}\approx 0.3825$. In fact, we prove such results for any fixed $0<\rho <1$.

20 pages, 1 figure