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
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.
of the edges of complete graphs. Here, the above are the only two colorings of all the edges of K16, which have no monochromatic triangles in any of the three colors. There are many other parameters to look at ... If you want to try yourself, get in touch with Professor Radziszowski.