Ramsey numbers involving large dense graphs and bipartite Turán numbers

Abstract

We prove that for any fixed integer m ≥ 3 and constants δ > 0 and α ≥ 0, if F is a graph on m vertices and G is a graph on n vertices that contains at least (δ - o(1))n2/(log n)α edges as n → ∞, then there exists a constant c = c(m, δ) > 0 such that r(F, G) ≥ (c - o(1)) (n/(log n)α+1)(e(F)-1)/(m-2) where e(F) is the number of edges F. We also show that for any fixed k ≥ m ≥ 2, r(Km,k,Kn) ≤ (k - 1 + o(1)) (n/log n)m as n → ∞. In addition, we establish the following result: For an m × k bipartite graph F with minimum degree s and for any E > 0, if k > m/E then ex(F;N) ≥ N2-1/s-e for all sufficiently large N. This partially proves a conjecture of Erdos and Simonovits. © 2002 Elsevier Science (USA). All rights reserved.