Nearly tight exponents for off-diagonal Ramsey numbers
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913168482107392 |
|---|---|
| author | Bradač, Domagoj |
| author_facet | Bradač, Domagoj |
| contents | We construct a new family of $K_s$-free graphs that leads to improved lower bounds for Ramsey numbers across a wide range of parameters. For any fixed $s \ge 4$, we show that the off-diagonal Ramsey numbers satisfy $r(s, k) \ge k^{s-2 + o(1)}.$ For $s \ge 6,$ this improves the best known lower bound of the form $r(s, k) \ge k^{\frac{s+1}{2} + o(1)}$ which was first established by Spencer in 1977 and has since only seen logarithmic improvements. This nearly matches the best known upper bound which is of the form $r(s, k) \le k^{s-1 + o(1)}$ and which is widely believed to give the correct exponent. More generally, we show that if $s, k/s \rightarrow \infty$, then $r(s, k) = \left(\frac{k}{s}\right)^{(1+o(1)) s},$ where the upper follows from the seminal work of Erdős and Szekeres in 1935. We also obtain improved lower bounds for Ramsey numbers extremely close to the diagonal as well as for diagonal multicolor Ramsey numbers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_28793 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Nearly tight exponents for off-diagonal Ramsey numbers Bradač, Domagoj Combinatorics We construct a new family of $K_s$-free graphs that leads to improved lower bounds for Ramsey numbers across a wide range of parameters. For any fixed $s \ge 4$, we show that the off-diagonal Ramsey numbers satisfy $r(s, k) \ge k^{s-2 + o(1)}.$ For $s \ge 6,$ this improves the best known lower bound of the form $r(s, k) \ge k^{\frac{s+1}{2} + o(1)}$ which was first established by Spencer in 1977 and has since only seen logarithmic improvements. This nearly matches the best known upper bound which is of the form $r(s, k) \le k^{s-1 + o(1)}$ and which is widely believed to give the correct exponent. More generally, we show that if $s, k/s \rightarrow \infty$, then $r(s, k) = \left(\frac{k}{s}\right)^{(1+o(1)) s},$ where the upper follows from the seminal work of Erdős and Szekeres in 1935. We also obtain improved lower bounds for Ramsey numbers extremely close to the diagonal as well as for diagonal multicolor Ramsey numbers. |
| title | Nearly tight exponents for off-diagonal Ramsey numbers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.28793 |