# On a geometric generalization of the Upper Bound Theorem

Wagner U. 2006. On a geometric generalization of the Upper Bound Theorem. FOCS: Foundations of Computer Science, IEEE Conference Proceedings, , 635–645.

Download

**No fulltext has been uploaded. References only!**

*Conference Paper*|

*Published*

Author

Series Title

IEEE Conference Proceedings

Abstract

We prove an upper bound, tight up to a factor of 2, for the number of vertices of level at most t in an arrangement of n halfspaces in R , for arbitrary n and d (in particular, the dimension d is not considered constant). This partially settles a conjecture of Eckhoff, Linhart, and Welzl. Up to the factor of 2, the result generalizes McMullen's Upper Bound Theorem for convex polytopes (the case ℓ = O) and extends a theorem of Linhart for the case d ≤ 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 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 ℓ. 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.

Publishing Year

Date Published

2006-06-08

Page

635 - 645

Conference

FOCS: Foundations of Computer Science

IST-REx-ID

### Cite this

Wagner U. On a geometric generalization of the Upper Bound Theorem. In: IEEE; 2006:635-645. doi:10.1109/FOCS.2006.53

Wagner, U. (2006). On a geometric generalization of the Upper Bound Theorem (pp. 635–645). Presented at the FOCS: Foundations of Computer Science, IEEE. https://doi.org/10.1109/FOCS.2006.53

Wagner, Uli. “On a Geometric Generalization of the Upper Bound Theorem,” 635–45. IEEE, 2006. https://doi.org/10.1109/FOCS.2006.53.

U. Wagner, “On a geometric generalization of the Upper Bound Theorem,” presented at the FOCS: Foundations of Computer Science, 2006, pp. 635–645.

Wagner, Uli.

*On a Geometric Generalization of the Upper Bound Theorem*. IEEE, 2006, pp. 635–45, doi:10.1109/FOCS.2006.53.