A Geometric Generalization of the Upper Bound Theorem

by Uli Wagner

Abstract:    
*********
Levels in arrangements are fundamental objects in discrete
and computational geometry. Let $\mathcal{A}$ be a set of
$n$ closed affine halfspaces in $\R^d$, which we can think
of as the constraints of a linear program. Then the level
of a point $x\in \R^d$ is defined as the number of constraints
that $x$ violates, i.e., the number of halfspaces that it is
\emph{not} contained in.

We prove an exact upper bound for the number of vertices of
level at most $\ell$ in an arrangement of $n$ halfspaces in
$\R^d$, for arbitrary $n$ and $d$ (in particular, the dimension
$d$ is not considered constant). This partially settles a
conjecture of Eckhoff, Linhart, and Welzl.

The result generalizes McMullen's Upper Bound Theorem for convex
polytopes (the case $\ell=0$). Furthermore, it extends a theorem
of Linhart for the case $d \leq 4$, and sharpens  asymptotic
bounds 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 using tools from multilinear algebra. This extends an
approach of Alon and Kalai, who used linear algebra methods
for 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$.

Furthermore, we discuss a connection with crossing numbers of
graphs that was one of the main motivations for investigating
exact bounds that are valid for arbitrary dimensions.