Grid Ramsey number rectangle vs clique

Status open high confidence

The Grid Ramsey problem gr(G_{2\times 2}, K_n) was introduced in arXiv:2210.03545 with bounds $2^{c\log^2 n} \le \mathrm{gr}(G_{2\times 2}, K_n) \le 2^{c'n^{2/3}\log n}$; no subsequent work has improved either bound. A 2025 paper by He et al. (arXiv:2511.01215) studied the broader family of grid Ramsey numbers and established that $G_{2\times 2}$ is exceptional — every other cycle $C \neq G_{2\times 2}$ satisfies $\mathrm{gr}(C, K_k) = k^{O_C(1)}$ — but the exact growth rate of $\mathrm{gr}(G_{2\times 2}, K_n)$ remains open.

Cited literature (1)

• partial Ramsey numbers of grid graphs (2025)
  Xiaoyu He, Ghaura Mahabaduge, Krishna Pothapragada, Josh Rooney, Jasper Seabold · arXiv preprint · arXiv:2511.01215

  Proves that $G_{2\times 2}$ is exceptional among grid graphs (all other cycles have polynomial grid Ramsey numbers), confirming the problem's difficulty, but does not improve the bounds $2^{\Omega(\log^2 k)} \le \mathrm{gr}(G_{2\times 2}, K_k) \le 2^{O(k^{2/3}\log k)}$.

Reviewer notes. The problem was introduced as a novel Ramsey-type question on grid graphs to prove the main result on $r(K^{(3)}_4, S^{(3)}_n)$. The 2025 paper arXiv:2511.01215 explicitly references the same bounds from 2210.03545 without improvement, confirming the exact growth rate of gr(G_{2\times 2}, K_n) is open as of late 2025.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).