Ramsey's Theorem - Asymptotics

Asymptotics

The inequality R(r, s) ≤ R(r − 1, s) + R(r, s − 1) may be applied inductively to prove that

In particular, this result, due to Erdős and Szekeres, implies that when r = s,

An exponential lower bound,

was given by Erdős in 1947 and was instrumental in his introduction of the probabilistic method. There is obviously a huge gap between these two bounds: for example, for s = 10, this gives 101 ≤ R(10,10) ≤ 48620. Nevertheless, exponential growth factors of either bound have not been improved to date and still stand at 4 and respectively. There is no known explicit construction producing an exponential lower bound. The best known lower and upper bounds for diagonal Ramsey numbers currently stand at

due to Spencer and Conlon respectively.

For the off-diagonal Ramsey numbers R(3,t), it is known that they are of order ; this may be stated equivalently as saying that the smallest possible independence number in an n-vertex triangle-free graph is . The upper bound for R(3,t) is given by Ajtai, Komlós, and Szemerédi, the lower bound by Kim. More generally, for off-diagonal Ramsey numbers R(s, t) with s fixed and t growing, the best known bounds are

due to Bohman and Keevash and Ajtai, Komlós and Szemerédi respectively.