# Combinatorial discrepancy for boxes via the ellipsoid-infinity
norm

## Aleksandar Nikolov, Rutgers University

## September 9, 2014

Tusnády's problem in $d$ dimensions asks for the smallest possible
value $\Delta_d(n)$ for which any $n$-point set $P$ in $\mathbb{R}^d$
can be two-colored so that no axis-aligned box has more than
$\Delta_d(n)$ points of one color in excess of the other. In 1981,
Beck showed that $\Delta_d(n)$ is bounded from below by the
Lebesgue-measure discrepancy of axis-aligned boxes, which is known
to be at least $\Omega(\log^{(d-1)/2} n)$. On the other hand, the
best known upper bound for $\Delta_d(n)$ is considerably larger: Larsen gave
a bound of $O(\log^{d + 1/2} n)$, slightly improving on a previous
result of Matoušek. We nearly close this gap and show a new
lower bound of $\Omega(\log^{d-1} n)$. We also give a new simple
proof of the upper bound. Our results are proved via the
ellipsoid-infinity norm, defined for a matrix $A$ as the the minimum
$\ell_\infty$ norm of a $0$-centered ellipsoid $E$ that contains
all column vectors of $A$. The ellipsoid-infinity norm approximates
hereditary discrepancy up to logarithmic factors and satisfies a
number of nice properties, such as the triangle inequality and
multiplicativity with respect to Kronecker products, making it
a powerful tool in combinatorial discrepancy theory.

Joint work with Jiří Matoušek.