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 it vertices not containing a complete graph K-s on s vertices. More than 40 years ago Erdos 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 Erdos. 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, 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 Erdos, Hajnal, Simonovits, Sos, and Szemeredi, we obtain for all 0 < delta < 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-delta). (c) 2004 Wiley Periodicals, Inc.