 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/ii/paper-2/14i/c/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 2 / 14I / c / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-06

The binomial upper bound for a Ramsey number gives

R (3, t) \leq (2 t + 1) = O (t^{2})

. For the triangle-free Ramsey lower bound by alteration, a binomial random graph

G (n, p)

has expected triangle count

(3 n) p^{3}

and expected independent

t

-set count

(t n) (1 - p)^{(2 t)}

. Choose a realization whose sum of these counts is at most its expectation. Delete one vertex from each surviving forbidden set, iterating through the originally listed sets. The remaining graph has neither a triangle nor an independent

t

-set. This random alteration method proves

R (3, t) > n - (3 n) p^{3} - (t n) (1 - p)^{(2 t)} .

(1)

For large

t

, set

n = ⌊(t / (4 lo g t))^{3/2} ⌋

and

p = n^{- 2/3}

. The triangle term is at most

n /6

. Using

(t n) \leq (e n / t)^{t}

and

1 - p \leq e^{- p}

, the logarithm of the independent-set term divided by

t

is at most

lo g (e n / t) - \frac{p ( t - 1 )}{2} \leq \frac{1}{2} lo g t - \frac{3}{2} lo g lo g t + O (1) - 2 lo g t + o (1),

(2)

which tends to

- \infty

. That term is eventually below

1

. Thus

R (3, t) > 5 n /6 - 1

and

R (3, t) = Ω ((t / lo g t)^{3/2}) .

(3)

 Read the full article

 New to topics? Read the docs here!