Given a positive integer $a$, the Ramsey number $R(a)$ is the least $n$ such that whenever the edges of the complete graph $K_n$ are colored using only two colors, we necessarily have a copy of $K_a$ with all its edges of the same color.
For example, $R(3)= 6$, which is usually stated by saying that in a party of 6 people, necessarily there are 3 that know each other, or 3 that don't know one another; but there is a party of 5 people without this property. This is probably known to everybody.
Slightly less known is the fact that any such coloring of $K_6$ in fact contains 2 monochromatic triangles.
The Ramsey multiplicity $m(a)$ (there does not seem to be a standard notation) is the largest number $m$ of monochromatic copies of $K_a$ that we can guarantee in any 2-coloring of $K_{R(a)}$. For example, $m(3)=2$, and Piwakowski and Radziszowski showed around 1999 that $m(4)=9$.
I have a couple of questions (please forgive me if they are trivial, I'm just beginning to form my intuitions in this field) :
-
Is it known that $m(n)$ is monotonically increasing?
-
Do we know anything about the rate of growth of the function $m(n)$?
I suspect that the answer to both questions is yes and that reasonable bounds for $m(n)$ are known, but haven't been able to locate any references. The best I know is that $$ m(n)\le \frac{\binom{r(n)}n}{2^{\binom n2-1}}, $$
(proved by Burr and Rosta in 1980), which is probably too high, and a recent result of Conlon suggests that
$$ m(n)\ge C\frac{\binom{r(n)}n}{2^{n(3n-1)/2}} $$
for some appropriate $C$. I say "suggests" because Conlon's results carry some additional implicit constants that I haven't checked can be absorbed this way. (Please let me know if I am completely off the mark here.) [Edit: Unfortunately, Conlon's bounds (in his paper "On the Ramsey Multiplicity of Complete Graphs") do not apply here. No lower bound beyond $m(n)\ge1$ seems known.]
"Update": William Gasarch's Open Problems column in the June 2020 issue of the ACM SIGACT News is devoted to Ramsey multiplicity.
Best Answer
I emailed David Conlon about this question. He agreed to let me share his answer. In short, the problem very much seems to be open (I've added the relevant tag). As Thomas mentions, the upper bound I cite is straightforward. And nothing better is known!
If one looks for papers on Ramsey multiplicity, a few come up, but they deal with a different concept, that I explain below. The quotes are from Conlon's emails.
Indeed, in the papers I have seen (included P-R, where $m(4)=9$ is proved), there are no arguments about $m(n)$ for general $n$ (or even $n=5$).
Here, $r(m,n)$ are the usual Ramsey numbers (what I called $R(n)$ in the question, is $r(n,n)$ in this notation). In general, $r(m,n)$ is the smallest $k$ such that any coloring of the edges of $K_k$ with blue and red either contains a blue copy of $K_m$ or a red copy of $K_n$.
Finally, as to the question of how to call this concept:
The usual Ramsey multiplicity is defined as follows. It is significantly better understood than $m(n)$.
Let $k_t(n)$ be the minimum number of monochromatic copies of $K_t$ within a two-coloring of the edges of $K_n$, and let $$ c_t(n)= \frac{k_t(n)}{\binom nt} $$ be the minimum proportion of monochromatic copies of $K_t$ in such a two-coloring.
It is known that the numbers $c_t(n)$ increase with $n$. The Ramsey multiplicity of $t$ (or of $K_t$) is $\displaystyle c_t\lim_{n\to\infty} c_t(n)$.
(Relevant references can be found in Conlon's paper mentioned in the question.)