Previous work on Ramsey multiplicity focused primarily on the multiplicity of complete graphs of constant size. We study the question for larger complete graphs, specifically showing that in every 2-coloring of a complete graph on @math vertices, there are at least @math monochromatic complete subgraphs of size between @math and @math . We also study bounds on the ratio between a maximum and a random red clique in a graph, and the ratio between a maximum and a random monochromatic clique in a graph.
Let G = (V,E) be a graph on n vertices with average degree t ≥ 1 in which for every vertex v ∈ V the induced subgraph on the set of all neighbors of v is r-colorable. We show that the independence number of G is at least c log (r+1) n t log t, for some absolute positive constant c. This strengthens a well known result of Ajtai, Komlos and Szemeredi. Combining their result with some probabilistic arguments, we prove the following Ramsey type theorem, conjectured by Erdos in 1979. There exists an absolute constant c′ > 0 so that in every graph on n vertices in which any set of b √ nc vertices contains at least one edge, there is some set of b √ nc vertices that contains at least c′ √ n log n edges. Let G be a regular graph of degree d on n points which contains no Kr (r ≥ 4). Let α be the independence number of G. Then we show for large d that α ≥ c(r)n ***image***. © 1995 John Wiley & Sons, Inc.