[home] - [up]


Lectures and Colloquia during the semester



October 28, 2002

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 042           - map -
Lecture - 14:15

Ioannis Z. Emiris - University of Athens

Toric resultants and mixed subdivisions

Abstract: The resultant of an overconstrained algebraic system is a polynomial in the input coefficients that vanishes iff the given equations have a common root. It generalizes the determinant of the coefficient matrix of an overconstrained linear system as well as Sylvester's resultant of 2 univariate polynomials. In general, resultants provide effective tools for studying and solving systems of algebraic equations.

More precisely, the toric resultant is able to capture the structure of the input polynomials by means of combinatorial geometric constructions. The theory of toric elimination associates each polynomial to its Newton polytope, defined as the convex hull of the exponent vectors of its nonzero terms. The Minkowski sum of all input Newton polytopes and its mixed subdivisions yield interesting information on the toric resultant.

In this talk, I shall discuss mixed subdivisions of Minkowski sums of convex polytopes in arbitrary dimension, starting with low-dimensional examples. We shall see how mixed subdivisions can be used to compute a multiple of the toric resultant or even the exact resultant itself. Moreover, the Newton polytope of the toric resultant can be derived from the mixed subdivisions, a fact with various practical applications. This survey presents the state-of-the-art and mentions certain open questions.


Colloquium - 16:00

Arnold Wassmer - Technische Universität Berlin

Bounds of the Topological Method

Abstract: For a given graph G Lovasz constructs a simplicial complex B(G) with a natural Z_2-structure i.e. every simplex has a unique antipodal brother. Its Z_2-index ind(B(G)) is the dimension of the smallest sphere S^d into which the complex can be mapped equivariantly. Lovasz proved this index as a lower bound for the chromatic number of the graph; chi(G) >= ind(B(G)) + 2. With this method Lovasz computed the chromatic number of the Kneser graphs. Now one could try to apply this method for example to the unit length graph of the plane R^2. The vertices of this graph are the points in the plane. They are connected by an edge if their distance is 1. We will show that the topological method can give at most the well known bound chi(R^2) >= 4.

More precisely our result is the following: If a graph G does not contain a complete bipartite graph K_l,m as a subgraph then the index of its complex B(G) is bounded by ind(B(G)) <= l+m-3.

This is joint work with Peter Csorba, Carsten Lange, and Ingo Schurr.


[home] - [up] - [top]