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.
The work most related to this paper is that of Sz ' e kely @cite_12 . He showed that for large enough @math , in any @math -coloring of a complete graph on @math vertices there are at least @math monochromatic complete subgraphs, and there is @math -coloring with at most @math monochromatic complete subgraphs. Our Theorem improves over his lower bound. In the same work, Sz ' e kely also provides upper bounds on Ramsey multiplicities for Half-Ramsey graphs. We prove lower bounds that match his upper bounds (up to low order terms). See Corollary .
@cite_12
1999589324
Let us defineG(n) to be the maximum numberm such that every graph onn vertices contains at leastm homogeneous (i.e. complete or independent) subgraphs. Our main result is exp (0.7214 log2 n) ≧G(n) ≧ exp (0.2275 log2 n), the main tool is a Ramsey—Turan type theorem.