On a geometric generalization of the Upper Bound Theorem

U. Wagner, in:, IEEE, 2006, pp. 635–645.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
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 U. 2006. On a geometric generalization of the Upper Bound Theorem. FOCS: Foundations of Computer Science, IEEE Conference Proceedings, 635–645.
Wagner, Uli. On a Geometric Generalization of the Upper Bound Theorem. IEEE, 2006, pp. 635–45, doi:10.1109/FOCS.2006.53.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar