There exist graphs with super‐exponential Ramsey multiplicity constant

The Ramsey multiplicity M ( G ; n ) of a graph G is the minimum number of monochromatic copies of G over all 2‐colorings of the edges of the complete graph K n . For a graph G with a automorphisms, ν vertices, and E edges, it is natural to define the Ramsey multiplicity constant C ( G ) to be $\lim_{{n} \to \infty} {M}(G;n){a/v}!{n \choose v}$ , which is the limit of the fraction of the total number of copies of G which must be monochromatic in a 2‐coloring of the edges of K n . In 1980, Burr and Rosta showed that 0 ≥  C ( G ) ≤ 2 1− E for all graphs G , and conjectured that this upper bound is tight. Counterexamples of Burr and Rosta's conjecture were first found by Sidorenko and Thomason independently. Later, Clark proved that there are graphs G with E edges and 2 E −1 C ( G ) arbitrarily small. We prove that for each positive integer E , there is a graph G with E edges and C ( G ) ≤  E − E /2 +  o ( E ) . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 89–98, 2008