[home] - [up] |
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.
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.