MIT Combinatorics Seminar

On a Geometric Generalization of the Upper Bound Theorem

Uli Wagner (Hebrew University of Jerusalem)

Wednesday October 18, 2006   4:15 pm    Room 2-136


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$.