A quadratic upper bound on the Chvátal rank of polytopes in the 0/1-cube
Abstract
We show that every polytope P⊆[0,1]n, and more generally every compact convex set, has Chvátal rank at most 12.22n2+nlog2 n+2n+4. This improves the O(n2log n) bound of Eisenbrand and Schulz and, together with the Ω(n2) lower bound of Rothvoß and Sanità, shows that the maximum Chvátal rank of a polytope in [0,1]n is Θ(n2). More precisely, if P contains an integer point, then for every c∈ℤn∖{0} the inequality cx≤max{cy: y∈ P∩ℤn} is valid for the k-th Chvátal closure of P for some k≤ 12.22n2+2n+2log2|c|∞+4. Following Eisenbrand and Schulz, we derive this inequality along a chain of coarser and coarser integer vectors, but instead of halving the vector in each step, we round τc for a scale τ chosen freely in each dyadic window [2−t−1,2−t]. The main new ingredient is a multiscale version of Dirichlet's approximation theorem, proved by an elementary volume argument: for every c∈ℝn, the ℓ1-distances of τc to ℤn, minimized within each dyadic window and summed over all windows, total less than 1.222n2, independently of |c|∞.
Related
- 0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problems
- A Quadratic Bound for Automorphism Groups of Curves of Positive p-Rank in Odd Characteristic
- On the Chvátal-Gomory Closure of Integer Quadratic Programs
- A Log-Free Lower Bound for the Number of Facets of 0/1-Polytopes
- Lower affine MV polytopes of rank 2
BibTeX
@misc{pia2026quadratic,
title = {{A quadratic upper bound on the Chvátal rank of polytopes in the 0/1-cube}},
author = {Alberto Del Pia},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32210},
eprint = {2609.32210},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32210},
}
RIS
TY - UNPB
TI - A quadratic upper bound on the Chvátal rank of polytopes in the 0/1-cube
AU - Alberto Del Pia
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32210
UR - https://arxiv.org/abs/2609.32210
AB - We show that every polytope P⊆[0,1]^n, and more generally every compact convex set, has Chvátal rank at most 12.22n^2+nlog_2 n+2n+4. This improves the O(n^2log n) bound of Eisenbrand and Schulz and, together with the Ω(n^2) lower bound of Rothvoß and Sanità, shows that the maximum Chvátal rank of a polytope in [0,1]^n is Θ(n^2). More precisely, if P contains an integer point, then for every c∈ℤ^n∖{0} the inequality cx≤max{cy: y∈ P∩ℤ^n} is valid for the k-th Chvátal closure of P for some k≤ 12.22n^2+2n+2log_2|c|_∞+4. Following Eisenbrand and Schulz, we derive this inequality along a chain of coarser and coarser integer vectors, but instead of halving the vector in each step, we round τc for a scale τ chosen freely in each dyadic window [2^−t−1,2^−t]. The main new ingredient is a multiscale version of Dirichlet's approximation theorem, proved by an elementary volume argument: for every c∈ℝ^n, the ℓ_1-distances of τc to ℤ^n, minimized within each dyadic window and summed over all windows, total less than 1.222n^2, independently of |c|_∞.
ER -