[home] - [up]


Lectures and Colloquia during the semester



June 3, 2002

Humboldt-Universität zu Berlin
Rudower Chaussee 5
12489 Berlin
Room 3.101           - map -
Lecture - 14.00 Uhr c.t.

Ingo Schiermeyer - Technische Universität Bergakademie Freiberg

Rainbow Colourings

Abstract: Für n \geq k \geq 3 sei f(n, C_k) die maximale Anzahl m von Farben, mit denen die Kanten des vollständigen Graphen K_n gefärbt werden können, so dass \ jeder Kreis C_k in K_n wenigstens zwei Kanten mit derselben Farbe enthält. Umgekehrt enthält jede Kantenfärbung des K_n mit wenigstens f(n,C_k) + 1 Farben einen Rainbow Kreis C_k. Erdos, Simonovits und Sós vermuten, dass für jedes k \geq 3, f(n, C_k) = n (\frac{k-2}{2} + \frac{1}{k-1}) + O(1) gilt. Für k = 3 haben sie f(n,C_3)=n-1 gezeigt und damit ihre Vermutung bewiesen. Alon hat f(n, C_4) = \lfloor \frac{4n}{3} \rfloor - 1 gezeigt und damit die Vermutung für k = 4 bewiesen.

In diesem Vortrag stellen wir f(n,C_5) und f(n,C_6) vor und beweisen damit die Vermutung für k = 5 und k = 6. Anschliess end stellen wir f(n,K_k) für alle n \geq k \geq 4 und f(n,kK_2) für alle k \geq 2 und n \geq 3k+3 vor.

[ps-file]


Colloquium - 16 Uhr s.t.

Mihyun Kang - Humboldt-Universität zu Berlin

Random walks

Abstract: Random walks or Markov chains are random processes with memoryless property. We consider random walks on finite graphs, which can be decomposed into several Cayley graphs of finite groups. Using group representations we investigate the probability distribution of the first hitting time, i.e., the minimum number of steps from an arbitrary element to another element.

Random walks can be used for generating or counting random objects, called Markov chain Monte Carlo methods. Prop-Wilson's coupling from the past (CFTP) generates random objects exactly according to the given probability distribution. It runs independently and in parallel the copies of a Markov chain and stops when all copies have coalesced. We consider a Markov chain on random outerplanar graphs and generate them uniformly at random using a version of CFTP. This is joint work with Manuel Bodirsky and Clemens Gröpl.


[home] - [up] - [top]