Construction of Ramsey graphs

Contact: Mahdi Cheraghchi
Room: BC 148
Tel: 021 6931316
Email: mahdi [dot] cheraghchi [at] epfl [dot] ch

The so-called “Ramsey theory” deals with the emergence of structure in large combinatorial objects. A very simple but familiar example is the pigeonhole principle: If we pick a “large enough” number of sample of the elements of a finite set, we will surely see repetitions. This project deals with one of the basic objects in this theory, namely, Ramsey graphs.

A Ramsey graph is a graph that has no “small” cliques (i.e., a set of vertices that are pairwise connected via the edges) or independent sets (i.e., a set of vertices none of which connected to the rest). Ramsey graphs with certain parameters are known to exist, but there is no known algorithm to efficiently construct them. There are, however, efficient algorithms can achieve non-trivial parameters, but these achievable parameters are still far from optimal.

The aim of this project is to study and understand the main known constructions of Ramsey graphs (and hopefully, including recent results) and their various connections with theoretical computer science. This project is suitable for Masters students with a theoretical interest.