Total disorder is impossible: an introduction to Ramsey Theory

Emeritus Professor Brendan McKay (RSCS)

Frank Ramsey was a Cambridge logician who died in 1930 at the age of 26.  With the ultimate goal of finding a "regular procedure to determine the truth or falsity of any given logical formula" (something that Godel proved impossible shortly afterwards), Ramsey proved a theorem which established a field of combinatorics now universally known as Ramsey Theory.

Examples of results in Ramsey Theory: (1) Van der Waerden's Theorem: For any k and c, if n is large enough and the integers 1..n are coloured using a set of c colours, there is a monochromatic arithmetic progression of length k; (2) Hales-Jewett Theorem: For any k and c, if n is large enough and the unit cubes of an n-dimensional cube of side k are coloured using c colours, there is a monochromatic line of k unit cubes.

The most well-known examples of Ramsey Theory involve colourings of graphs and hypergraphs.  We will provide definitions and examples, with emphasis on unsolved problems and asymptotics.

Ramsey Number Upper Bounds

Dr Vigleik Angeltveit (MSI)

The Ramsey number R(s,t) is the smallest n such that any graph on n vertices contains either s vertices that are all adjacent or t vertices that are all non-adjacent. These numbers are only known for small values of s and t. In particular R(5,5) is not known. I will explain how to improve the upper bound on R(5,5) from 49 to 46, and how to improve the upper bound on almost every unknown Ramsey number. This is all joint work with Brendan McKay.