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]