# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# Monday Lecture and Colloquium

November 17 , 2008

Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

### Modern Algorithmic Mathematics: Between Randomness and Determinism

Abstract:
With classical algorithmics naturally being deterministic, it was quite a revolution when randomized algorithms became highly successful in the last 30 years.

Nowadays, randomized algorithms are well-established. For many problems, randomized algorithms are currently the best known solution. Surprisingly, in most cases these algorithms are quite simple. Often, it suffices to make all decisions independently at random. However, recent results suggest that a more careful use of randomness may yield even superior results.

In the talk, I shall first demonstrate the success of independent randomized methods. I will then show (i) how to gain improvements by using the right dose of randomness, and (ii) how one can still analyze thus random experiments in spite of the dependencies.

Colloquium - 16:00

### Tropical Riemann-Roch, chip firing, and tropical polytopes

Abstract:
A finite graph can be viewed, in many respects, as a discrete analogue of a Riemann surface. We pursue this analogy in the context of linear equivalence of divisors. A divisor $D$ on a graph $G=(V,E)$ is a $\Z$-linear combination of vertices. $$D = \sum_{v \in V} D(v) \cdot v \quad \in \ \text{ with } D(v) \in \Z$$ We consider $D$ as a vector in $\R^V$. Then we call two divisors linearly equivalent, $D \sim D'$, if $D-D' \in \ker L$, where $L \colon \R^V \to \R^V$ is the Laplace matrix of $G$. This notion of equivalence can be formulated in terms of Bj\"orner/Lov\'asz/Shor's chip firing game.

Many classical results on Riemann surfaces have analogues in this setting. Most notably, there is an analogue of the Riemann-Roch Theorem [Baker/Norine 2006]. Most of these results can be generalized to tropical curves'' which are essentially metric graphs [Gathmann/Kerber 2006, Mikhalkin/Zharkov 2006, Hladk\'y/Kr\'al'/Norine 2007].

Riemann-Roch is a statement about linear systems of divisors. Classically, a linear system is a projective space. Tropically, a linear system is a polyhedral complex which looks like a tropical polytope, but isn't.

This will be joint work with Josephine Yu and Gregg Musiker (MIT).

Letzte Aktualisierung: 11.11.2008