0
$\begingroup$

Let $q\geq 1$ and $H_1,\dots, H_q$ be graphs.

By Ramsey theorem, it is well-known that there exists $n_0$ such that the following holds.

If $n\geq n_0$ and the edges of $K_n$ are colored with $q$ colors, then there exists an $i\in\{1,\ldots,q\}$ such that there exists a monochromatic copy of $H_i$ in color $i$.

The following quantitative version also holds.

There exist positive constants $c>0$ and $n_0$ such that, if $n\geq n_0$ and the edges of $K_n$ are colored with $q$ colors, then there exists an $i\in\{1,\ldots,q\}$ such that there are at least $c n^{|V(H_i)|}$ monochromatic copies of $H_i$ in color $i$.

It is often quoted as "Folklore", and I know it is not too difficult to prove. I've found some related theorem (often related to Ramsey-multiplicities, e.g, this article by Burr and Rosta), but not covering the multicolor / asymmetric case. For completeness, I would like to insert an actual reference in an article.

$\endgroup$
2
  • $\begingroup$ This immediately follows from the usual Ramsey theorem by averaging over subsets of size $N$=Ramsey number. So most probably it was not published as a separate result, and many people got it independently. $\endgroup$ Oct 23 '20 at 12:04
  • $\begingroup$ @FedorPetrov yep that's my guess. I know the proof, I could write a summary of it. I was just hoping for some reference. Thanks $\endgroup$ Oct 24 '20 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.