We prove an upper bound, sharp up to a factor of 2, for the number of
vertices of level at most $\ell$ in an arrangement of $n$ halfspaces in
$\mathbb R^d$, for arbitrary $n$ and $d$ (in particular, the dimension $d$ is
not considered constant). This partially settles a conjecture due to
Eckhoff, Linhart, and Welzl.
Up to the factor of 2, the result generalizes McMullen's Upper Bound Theorem
for convex polytopes (the case $\ell=0$) and extends a theorem of Linhart
for the case $d \leq 4$. Moreover, the bound sharpens asymptotic
estimates obtained by Clarkson and Shor.
The proof is based on the $h$-matrix of the arrangement (a generalization,
introduced by Mulmuley, of the $h$-vector of a convex polytope). We show
that bounding appropriate sums of entries of this matrix reduces to a lemma
about quadrupels of sets with certain intersection properties, and we prove
this lemma, up to a factor of 2, using tools from multilinear algebra. This
extends an approach of Alon and Kalai, who used a similar lemma for pairs of
sets to give an alternative proof of the classical Upper Bound Theorem.
The bounds for the entries of the $h$-matrix also imply bounds for the
number of $i$-dimensional faces, $i>0$, at level at most $\ell$ but in
general these are less satisfying than in the case $\ell=0$.