---- dataentry project ----
title : Construction of Ramsey graphs
contactname: Mahdi Cheraghchi
contactmail_mail: mahdi.cheraghchi@epfl.ch
contacttel: 021 6931316 
contactroom: BC 148
type : master semester
state : completed
table : projects
created_dt : 2009-01-01
taken_dt : 
completed_dt :
by : Gaël Cotting
output_media :
======
template:datatemplates:project
----

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.