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 , 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?1C(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