RIT Computer Science

Computational Ramsey Theory

Department of Computer Science, RIT



Lead faculty: Stanisław Radziszowski
room: 70-3657, phone: (585) 475-5193
email: spr@cs.rit.edu
url: http://www.cs.rit.edu/~spr

part of CS Theory Theme


Summary

Ramsey theory is often regarded as the study of how order emerges from randomness. It has applications in parallel programming, approximation algorithms, game theory, geometry, number theory, and other areas of mathematics and theoretical computer science. The central concept in Ramsey theory is that of arrowing. For graphs F, G, and H, we say that F arrows (G,H) if and only if for every coloring of the edges of F with the colors red and blue, F contains a red G or a blue H. The Ramsey number of graphs G and H is the smallest n such that the complete graph on n vertices arrows (G,H).

There is very rich literature on Ramsey theory, starting with the seminal paper by Frank Plumpton Ramsey in 1930. The subject first concerned mathematical logic, but over the years it found its way into several areas of mathematics, computing, finance, economics and other fields. Ramsey theory studies the conditions of when a combinatorial object necessarily contains some smaller given objects. The role of Ramsey numbers is to quantify some of the general existential theorems in Ramsey theory. The Ramsey arrowing operator is a fundamental predicate used to describe such relationships.

The determination of whether this arrowing holds is notoriously difficult, and one has to deal with it in almost all cases of Ramsey-type problems. The goal of our research is to enhance known and develop new methods to decide if Ramsey arrowing holds in a general or particular situation. If we succeed, then we obtain new values or bounds on some concrete Ramsey or Folkman numbers.


Links to our papers


Links to general information