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.