Large K r ‐free subgraphs in K s ‐free graphs and some other Ramsey‐type problems

In this paper we present three Ramsey‐type results, which we derive from a simple and yet powerful lemma, proved using probabilistic arguments. Let 3 ≤ r < s be fixed integers and let G be a graph on n vertices not containing a complete graph K s on s vertices. More than 40 years ago Erdős and Rogers posed the problem of estimating the maximum size of a subset of G without a copy of the complete graph K r . Our first result provides a new lower bound for this problem, which improves previous results of various researchers. It also allows us to solve some special cases of a closely related question posed by Erdős. For two graphs G and H , the Ramsey number R ( G, H ) is the minimum integer N such that any red‐blue coloring of the edges of the complete graph K N , contains either a red copy of G or a blue copy of H . The book with n pages is the graph B n consisting of n triangles sharing one edge. Here we study the book‐complete graph Ramsey numbers and show that R ( B n , K n ) ≤ O ( n 3 /log 3/2 n ), improving the bound of Li and Rousseau. Finally, motivated by a question of Erdős, Hajnal, Simonovits, Sós, and Szemerédi, we obtain for all 0 < δ < 2/3 an estimate on the number of edges in a K 4 ‐free graph of order n which has no independent set of size n 1‐δ . © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005