AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Intuitively speaking, Ramsey theory is a branch of combinatorics that deals with order arising in large disordered structures. In the context of graphs we say that a graph G is F-Ramsey if any two-coloring of the edges of G contains a monochromatic copy of F. Ramsey's celebrated theorem states that the complete graph K_N is K_\ell-Ramsey for large enough N=N(\ell); the toy version of this theorem is the popular exercise in introductory courses to show that K_6 is K_3-Ramsey. While Ramsey's theorem seems to rely on the fact that a large complete graph is very dense, Folkman proved the surprising fact there are K_\ell-Ramsey graphs that do not contain a K_{\ell+1} as a subgraph (e.g., there are K_3-Ramsey graphs that are K_4-free). Forbidding a clique of size \ell+1 is an entirely local density restriction and still allows for Ramsey graphs with many edges. Rödl and Rucinski therefore raised the question how globally sparse F-Ramsey graphs G can possibly be, where sparseness is measured by the average degree, maximized over all subgraphs of G. In this talk we will discuss this so-called Ramsey density for various classes of graphs F and highlight some interesting phenomena.

Joint work with Ueli Peter.

Reto Spöhel

--email hidden

passcode not visible

logged in users only

Ramsey theory