Ramsey Theory of Graphs and Hypergaphs

The subject of the project lies within one of the classical areas of discrete mathematics, called Ramsey theory.

This area studies the phenomenon that every system, no matter how chaotic it migth look at first, contains a large completely homogeneous subsystem.

More precisely, the celebrated theorem of Ramsey from 1930 states that any graph (or more generally r-uniform hypergraph) on N vertices contains either a complete subgraph of size s, or an empty subgraph of size n, assuming N is sufficiently large with respect to s and n. The central problem in Ramsey theory is to understand how the minimal such N=N(s,n) depends on s and n.

It has been observed for several decades that imposing certain mild restrictions on the graph can change the answer drastically.

These restrictions can be structural, where some of the central problems are the Erdős-Hajnal conjecture and the Gyárfás-Sumner conjecture; geometric, involving coloring and so called chi-boundedness problems going back to the 60´s to a work of Asplund and Grünbaum; or algebraic, starting with the pioneering work of Alon, Pach, Pinchasi, Radoičić  and Sharir.

The project proposes to study some of the long-standing open problems in these areas along with newer research directions. Moreover, we consider variants of these problems in hypergraphs with a goal to build a general theory.