Combinatorics Seminar
When: Sunday, Dec. 5, 10am
Where: Schreiber 309
Speaker: Uli Wagner, Hebrew University
Title: On a Generalization of the Upper Bound Theorem
Abstract:
The Upper Bound Theorem, proved by McMullen in 1971, determines the
maximum number of vertices of a convex polyhedron $P$ that is given as
the intersection of $n$ affine halfspaces in $d$-dimensional Euclidean
space and gives a characterization when this maximum is attained (in
fact, the extremal "polar-to-neighborly" polyhedra simultaneously
maximize the number of $i$-dimensional faces for all $i$, $0\leq i \leq
d-1$).
Consider the following generalization of the extremal problem to $(\leq
k)$-levels: Let us define the level of a point $x$ to be the number of
halfspaces that it is NOT contained in (if we think of the halfspaces
as the constraints of some linear program, then the level of a point is
the number of constraints that it violates). Now, what is the maximum
number of vertices (intersections of $d$ bounding hyperplanes) whose
level does not exceed a given threshold $k$?
The conjectured answer, first formulated by Eckhoff, is that this
number is again maximized by the polar-to-neighborly arrangments. This
is known to be true for small dimensions, and to be asymptotically
correct for any fixed dimension $d$, but in its exact form, the
conjecture remains unresolved in general.
The goal of this talk is mostly to convince you that this is a very
interesting conjecture, by discussing connections with a number of
other problems, such as the Generalized Lower Bound Theorem, and
crossing numbers of complete graphs.