OurBigBook.comSite Source code

Binomial upper bound for a Ramsey number

The off-diagonal recursion

R (s, t) \leq R (s - 1, t) + R (s, t - 1)

with

R (1, t) = R (s, 1) = 1

gives

R (s, t) \leq (s - 1 s + t - 2) .

In particular,

R (t) \leq (t - 1 2 t - 2) < 2^{2 t}

.

 Ancestors (7)

 Incoming links (1)

Solution