Off-diagonal Ramsey numbers
For positive integers $s$ and $k$, the Ramsey number $r(s,k)$ is the minimum integer $n$ such that any graph on $n$ vertices contains a clique of size $s$ or an independent set of size $k$. We prove that for any fixed $s \ge 3$ and $k$ tending to infinity, the off-diagonal Ramsey numbers satisfy \[ r(s, k) \ge Ω\left(\frac{k^{s-1}}{(\log k)^{2s-4}} \right), \] which matches, up to polylogarithmic factors, the upper bound established over 90 years ago by Erdős and Szekeres. For $s \ge 5,$ this improves the best known lower bound of the form $r(s, k) \ge k^{\frac{s+1}{2} + o(1)}$ which was…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.28793
curl -X POST /api/v1/records/arxiv/2605.28793/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.28793/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'