[home] - [up]


Lectures and Colloquia during the semester



Monday, June 12, 2006

Humboldt-Universität zu Berlin
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett, 1st floor, between house III and IV           - map -
Lecture - 14:15

Angelika Steger - ETH Zürich

The sparse regularity lemma and its consequences for random graphs

Abstract: Over the last decades Szemer\'edi's regularity lemma has proven to be a very powerful tool in modern graph theory. Unfortunately, in its original setting it only gives nontrivial results for dense graphs, that is graphs with $\Theta(n^2)$ edges. In 1996 Kohayakawa and independently R\"odl introduced a variant which holds for sparse graphs, provided they satisfy some additional structural conditions (which essentially mean that the graph does not contain too dense spots). However, using this sparse regularity lemma to prove e.g.\ extremal and Ramsey type results similar to the known results in the dense case, requires as an additional step the existence of appropriate embedding or counting lemmas. For the sparse case this missing step has been formulated as a conjecture by Kohayakawa, \L{}uczak and R\"odl in 1996. In this talk we prove a weak version of the KLR-conjecture and present various applications in random graph theory.


Colloquium - 16:00

Eric Fusy - Laboratoire d'Informatique (LIX)

Counting unrooted maps using tree-decomposition

Abstract: The terminology of maps refers to graphs embedded on a surface. Like in the case of trees, rooted objects are easier to count than unrooted ones, which are subject to symmetries. In this talk we present a new method to count several families of unrooted maps on the sphere, using a decomposition of a map into a tree-structure. As a main application, we are able to count efficiently unrooted 3-connected maps, corresponding to oriented combinatorial polytopes in 3D-space.


[home] - [up] - [top]