Séminaire Bourbaki du vendredi

Bounds for Ramsey numbers

by Timothy Gowers

Europe/Paris
Amphithéâtre Hermite (Institut Henri Poincaré)

Amphithéâtre Hermite

Institut Henri Poincaré

Description

  Ramsey's theorem in its most basic form states that for every $k$ there exists $k$ such that if the edges of a complete graph with $n$ vertices are coloured red or blue, then there must be $k$ vertices joined entirely by red edges or $k$ vertices joined entirely by blue edges. The question of how large $n$ must be to guarantee this is a major open problem in combinatorics, on which there has been major progress. 

Ramsey's theorem has many variants and generalizations. For example, one can consider more colours, or one can look at hypergraphs instead of graphs, or one can attempt to find monochromatic subgraphs other than cliques. This talk will discuss the quantitative aspects of these related problems. For most of them, there are large gaps between the best known upper and lower bounds, but there has been interesting progress on several of them, some of which is quite recent.