[home] - [up]

Lectures and Colloquia during the semester

Monday, November 6, 2006

Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
1st floor, between house III and IV

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

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

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.

[home] - [up] - [top]