On a geometric generalization of the Upper Bound Theorem Conference Paper

Author(s): Wagner, Uli
Title: On a geometric generalization of the Upper Bound Theorem
Title Series: 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.
Keywords: theorem proving; Asymptotic analysis; Linear algebra
Conference Title: FOCS: Foundations of Computer Science
Conference Dates: October 21-24, 2006
Publisher: IEEE  
Date Published: 2006-06-08
Start Page: 635
End Page: 645
DOI: 10.1109/FOCS.2006.53
Open access: no
IST Austria Authors
  1. Uli Wagner
    50 Wagner
Related IST Austria Work