 Triangle-free Ramsey lower bound by alteration

ID: triangle-free-ramsey-lower-bound-by-alteration

Sampling

G (n, p)

and deleting one vertex per triangle and per independent

t

-set gives

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

. Choosing

n

of order

(t / lo g t)^{3/2}

and

p

of order

lo g t / t

makes the forbidden configurations inexpensive enough to prove the corresponding lower bound.

 New to topics? Read the docs here!