Lectures and Colloquia during the semester

**Monday, November 6, 2006**

Humboldt-Universität zu Berlin

Institut für Informatik

Rudower Chaussee 25

12489 Berlin

Humboldt-Kabinett

1st floor, between house III and IV

ATTENTION ROOM CHANGE:

The Lecture (14:15h) takes place in house I, room no. 410

** Lecture - 14:15**

### Hans Jürgen Prömel - HU Berlin

### Probabilistic methods: The chromatic number of a random graph

*Abstract:*

The question
"What is the chromatic number of a random graph?"
will guide us through this talk. Erdös and Rényi (1960) first raised
this question in their seminal paper "On the evolution of random graphs".
As in many other areas of graph theory, the task to understand the
behaviour
of the chromatic number (and its smaller brother the clique number) led
to the development of new methods and revealed bridges to other areas of
mathematics.
We will start discussing this question by using the moment methods, then
introducing some concentration results for graphs and finally shed some
light
on the most recents achievements in this area due to Achlioptas, Naor
and others.
On the way, several questions and open problems will be mentioned.

**Colloquium - 16:00**

### Stefan Hougardy - HU Berlin

### Matching Algorithms

*Abstract:*

The matching problem is one of the basic problems in combinatorial
optimization. In 1965 Edmonds presented the first polynomial time
algorithm for this problem. Nowadays there exist several efficient
algorithms for solving the matching problem. Most of them use the concept
of augmenting paths. In this talk we will focus on algorithms for the
matching problem that do not need augmenting paths and discuss some open
problems in the area of matching algorithms.