Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Fritz Eisenbrand - EPF Lausanne

Constrained Minkowski Sums

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

Uwe Schauz - TU Berlin

Algebraically Solvable Problems: Describing Polynomials as Equivalent to Explicit Solutions

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.

Letzte Aktualisierung: 23.05.2008