[home] - [up]

Lectures and Colloquia during the semester

Monday, October 25, 2004

Humboldt-Universität zu Berlin
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett, 1st floor, between house III and IV           - map -
Lecture - 14.00 Uhr c.t.

Anusch Taraz - Technische Universität München

Colourings with few colours locally but many colours globally

Abstract: In this talk we consider edge colourings of the complete r-uniform hypergraph. Our central question will be: how `colourful' can such a colouring be globally if we restrict the number of colours locally?

The local restriction is formulated as follows: for a fixed hypergraph H and an integer k we call a colouring (H,k)-local, if every copy of H in the complete hypergraph picks up at most k different colours. We will investigate the threshold for k which guarantees that every local colouring must have a bounded global number of colours. However, we will also prove that just after the threshold local colourings are still `essentially bounded' in that they can exhibit their potential richness in colours only on a vanishing proportion of the edges.

As the proof of the latter relies on showing that any essentially unbounded colouring must be at least as colourful as a non-monochromatic canonical colouring, I will also give a gentle introduction to canonical colourings of hypergraphs and, briefly, arithmetic progressions with many colours.

This is joint work with B. Bollobás, Y. Kohayakawa, V. Rödl and M. Schacht.

Colloquium - 16 Uhr s.t.

Manuel Bodirsky -Humboldt-Universität zu Berlin

The asymptotic number of series-parallel graphs

Abstract: A series-parallel graph is a graph without a K_4-minor. We derive equations for the exponential generating function of (labeled) series-parallel graphs, analyse their singularities, and derive the asymptotic number of series-parallel graphs. With analytic tools we can also answer many questions about properties of random series-parallel graphs.

Joint work with Omer Gimenez, Mihyun Kang, and Marc Noy.

[home] - [up] - [top]