PreprintCC BY-NC-ND 4.0arXiv
The Lasserre Rank of the Cropped Hypercube
Abstract
In an n-dimensional cropped hypercube each of the 2n cropping inequalities chops off a single corner of the $0−−1$ hypercube by an ℓ1-distance ρ. The case ρ= 1/2 has been extensively studied in the literature. This paper shows that the Lasserre rank of the n-dimensional cropped hypercube where ρ= 1/2, n ≥ 2, is the smallest integer 0≤ t ≤ n such that Δt < 0 in the recurrence Δ−1 = 1, Δ0 = n−1, Δt = (n−1)Δt−1 − t(n−t+1)Δt−2. It follows that the Lasserre rank can be computed in time O(n2 log2 n). Asymptotically, the rank is n/2 + c1/2√n + o(√n), where c1/2 is the unique zero of a given function. Numerically, c1/2 ≈ 0.3825. In fact, we prove such results for any fixed 0 < ρ< 1.
Related
- Convergence Rates for Lasserre's Upper-Bound Hierarchy on ℝd with Gaussian Measure
- Hypercube eigenfunctions with two strong nodal domains
- Bootstrap percolation on the hypercube
- Average pairwise Hamming distance of a subset in a hypercube
- Mixing time of the lazy and simple random walk on a randomly twisted hypercube
BibTeX
@misc{cornuejols2026lasserre,
title = {{The Lasserre Rank of the Cropped Hypercube}},
author = {Gérard Cornuéjols and Vrishabh Patil and Jiaye Wei},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.27748},
eprint = {2609.27748},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27748},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - The Lasserre Rank of the Cropped Hypercube
AU - Gérard Cornuéjols
AU - Vrishabh Patil
AU - Jiaye Wei
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.27748
UR - https://arxiv.org/abs/2609.27748
AB - In an n-dimensional cropped hypercube each of the 2^n cropping inequalities chops off a single corner of the $0−−1$ hypercube by an ℓ_1-distance ρ. The case ρ= 1/2 has been extensively studied in the literature. This paper shows that the Lasserre rank of the n-dimensional cropped hypercube where ρ= 1/2, n ≥ 2, is the smallest integer 0≤ t ≤ n such that Δ_t < 0 in the recurrence Δ_−1 = 1, Δ_0 = n−1, Δ_t = (n−1)Δ_t−1 − t(n−t+1)Δ_t−2. It follows that the Lasserre rank can be computed in time O(n^2 log^2 n). Asymptotically, the rank is n/2 + c_1/2√n + o(√n), where c_1/2 is the unique zero of a given function. Numerically, c_1/2 ≈ 0.3825. In fact, we prove such results for any fixed 0 < ρ< 1.
ER -