Monday, June 9, 2008
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041
Lecture - 14:15
Abstract:
We consider the following problem. Given two finite point-sets in
the plane, a convex polygon and a quasi-convex objective function,
determine a point of the Minkowski sum of the two point-sets which
is contained in the polygon and maximizes the objective function. We
present an optimal algorithm for this task if the number of facets
of the polygon is fixed. We also present an O(n^{4/3}) upper bound
on the number of vertices of the convex hull of an arbitrary subset
of the Minkowski sum of two planar point-sets.
The talk is based on joint work with
Thorsten Bernholt, Thomas Hofmeister, Janos Pach, Thomas Rothvoss and
Nir Sopher
Colloquium - 16:00
Abstract:
We present a coefficient formula which provides some information about the
polynomial map $P| I1 x ... x In$ when only incomplete information about the
polynomial $P(X1,...,Xn)$ is given. It is an integrative generalization and sharpening
of several known results and has many applications, among these are:
1. The fact that polynomials $P(X1)\neq0$ in just one variable have at most $\deg(P)$ roots.
2. Alon and Tarsi's Combinatorial Nullstellensatz.
3. Chevalley and Warning's Theorem about simultaneous zeros of polynomials over finite fields.
4. Ryser's Permanent Formula.
5. Alon's Permanent Lemma.
6. Alon and Tarsi's Theorem about orientations and colorings of graphs.
7. Scheim's formula for the number of edge n-colorings of planar n-regular graphs.
8. Alon, Friedland and Kalai's Theorem about regular subgraphs.
9. Alon and F$uuml;redi's Theorem about cube covers.
10. Cauchy and Davenport's Theorem from additive number theory.
11. Erdös, Ginzburg and Ziv's Theorem from additive number theory.