Bounds on the Critical Multiplicity of Ramsey Numbers with Many Colors
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909587651690496 |
|---|---|
| author | Christopherson, Bryce Steinhaus, Casia |
| author_facet | Christopherson, Bryce Steinhaus, Casia |
| contents | The Ramsey number $R(s,t)$ is the least integer $n$ such that any coloring of the edges of $K_n$ with two colors produces either a monochromatic $K_s$ in one color or a monochromatic $K_t$ in the other. If $s=t$, we say that the Ramsey number $R(s,s)$ is diagonal. The critical multiplicity of a diagonal Ramsey number $R(s,s)$, denoted $m(s,s)$ or $m_2(s)$, is the smallest number of copies of a monochromatic $K_s$ that can be found in any coloring of the edges of $K_{R(s,s)}$. For instance, $m_2(2)=1$, $m_2(3)=2$, and $m_2(4)=9$. In this short note, we produce some new upper bounds for the general non-diagonal case of $m(s_1,...,s_k)$ and improve the bounds on $m_2(s)$ for small $s$. This appears to be the first progress on bounding the critical multiplicity of Ramsey numbers since Piwakowski and Radziszowski's 2001 determination that $m_2(4)=9$, and we are not aware of any subsequent improvements on this quantity in the literature. We conclude by outlining a reasonably clear path to further improvements. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_18869 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounds on the Critical Multiplicity of Ramsey Numbers with Many Colors Christopherson, Bryce Steinhaus, Casia Combinatorics 05D10, 05C55 The Ramsey number $R(s,t)$ is the least integer $n$ such that any coloring of the edges of $K_n$ with two colors produces either a monochromatic $K_s$ in one color or a monochromatic $K_t$ in the other. If $s=t$, we say that the Ramsey number $R(s,s)$ is diagonal. The critical multiplicity of a diagonal Ramsey number $R(s,s)$, denoted $m(s,s)$ or $m_2(s)$, is the smallest number of copies of a monochromatic $K_s$ that can be found in any coloring of the edges of $K_{R(s,s)}$. For instance, $m_2(2)=1$, $m_2(3)=2$, and $m_2(4)=9$. In this short note, we produce some new upper bounds for the general non-diagonal case of $m(s_1,...,s_k)$ and improve the bounds on $m_2(s)$ for small $s$. This appears to be the first progress on bounding the critical multiplicity of Ramsey numbers since Piwakowski and Radziszowski's 2001 determination that $m_2(4)=9$, and we are not aware of any subsequent improvements on this quantity in the literature. We conclude by outlining a reasonably clear path to further improvements. |
| title | Bounds on the Critical Multiplicity of Ramsey Numbers with Many Colors |
| topic | Combinatorics 05D10, 05C55 |
| url | https://arxiv.org/abs/2501.18869 |