What are the current best lower bounds for off-diagonal Ramsey numbers $R(k,l)$ with $l$ of order unity and asking for asymptotic behavior for large $k$, such as $R(k,4)$, $R(k,5)$, and so on? (please include any log factors, too!) Other than the more complicated arguments of Kim for $R(k,3)$, are all the other best lower bounds from the Lovasz local lemma?
[Math] Best lower bound for off-diagonal Ramsey numbers
co.combinatoricslower boundsramsey-theory
Related Solutions
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.
Unfortunately, the concept you're talking about is also known as the Ramsey multiplicity! There are very few references as far as I know. The only one I can think of offhand is the Piwakowski and Radziszowski paper which you quoted. Perhaps there's something in the references to that paper, but I doubt it somehow.
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$).
The function you're interested in is rather amorphous, I'm afraid. My result will imply that if $n \ge 4^t$ you must have at least $n^t/2^{3t^2/2}$ copies of $K_t$ or thereabouts. But when your number is below $4^t$ it implies nothing.
In general, because we don't understand the Ramsey function, I find it hard to imagine how we might be able to say anything at all about $m(n)$. Unless there's an elementary argument which gives something. It reminds me of estimating the difference between successive Ramsey numbers like $r(n,n)$ and $r(n,n+1)$, where, though the difference is almost certainly exponential, the largest difference that can be guaranteed is tiny (I think linear or quadratic even, though I can't remember exactly).
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$.
The only thing that appears clear to me is an upper bound following from the probabilistic method, namely $\displaystyle \frac{\binom{r(n)}{n}}{2^{\binom n2}}$. It's not even obvious how one would approach showing that the multiplicity is at least 2!
Finally, as to the question of how to call this concept:
I'd suggest that this be called the critical multiplicity or something like that, just to distinguish it from the usual multiplicity function.
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.)
The best known explicit Ramsey graph construction is in the paper:
Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson: 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. STOC 2006: 671-680
Call a graph $K$-Ramsey if it doesn't have a $K$-clique or a $K$-independent set. They prove
There is an absolute constant $\alpha > 0$ and an explicit construction of a $2^{2^{\log^{1−\alpha} n}} = 2^{n^{o(1)}}$-Ramsey graph over $2^n$ vertices, for every large enough $n \in {\mathbb N}$.
Here, "explicit construction" means roughly that there is an efficient algorithm which when given the string of $N$ ones, it outputs an $N$-node $K$-Ramsey graph. (I know this is "stronger" than what you would like, but you should still check these things out for fun.)
Before the above paper, the best known explicit construction was by Frankl and Wilson, who showed that there are $2^n$ node graph that are about $2^{\Omega(\sqrt{n})}$-Ramsey. Noga Alon had an alternative construction but I think it only matched Frankl and Wilson. See the above paper for more details.
All these constructions are very neat and use radically different methods from simple counting arguments, so I hope you enjoy them. You may find that the problem of finding a succinct/effective description of a family of lower bound graphs is indeed interesting.
Best Answer
The best bounds I know of are due to Tom Bohman for $R(k,4)$ and Bohman and Peter Keevash for $R(k,5)$ and beyond. Both rely on using the differential equations method to analyze the following process: Start with the empty graph, and at each step add an edge uniformly at random among all edges which do not create a $K_t$. The bounds they achieve are $$R(k,t) \geq c_t \left( \frac{k}{\log k} \right)^{\frac{t+1}{2}} (\log k)^{\frac{1}{t-2}}$$
The final term in this product corresponds to the improvement over the bounds obtained using the Local Lemma. For $t=3$ it matches Kim's bound up to a constant factor.