Ramsey numbers of grid graphs

Abstract

Let the grid graph $G_{M\times N}$ denote the Cartesian product $K_M\square K_N$. For a fixed subgraph $H$ of a grid, we study the off-diagonal Ramsey number $\mathrm{gr}(H,K_k)$, which is the smallest $N$ such that any red/blue edge coloring of $G_{N\times N}$ contains either a red copy of $H$ (a copy must preserve each edge's horizontal/vertical orientation), or a blue copy of $K_k$ contained inside a single row or column. Conlon, Fox, Mubayi, Suk, Verstraëte, and the first author recently showed that such grid Ramsey numbers are closely related to off-diagonal Ramsey numbers of bipartite $3$-uniform hypergraphs, and proved that $2^{\hat{I}\text{c◯}({\log }^{2}k)}\le \mathrm{gr}(G_{2\times 2},K_k)\le 2^{O(k^{2/3}\log k)}$. We prove that the square $G_{2\times 2}$ is exceptional in this regard, by showing that $\mathrm{gr}(C,K_k)=k^{O_C(1)}$ for any cycle $C\ne G_{2\times 2}$. We also obtain that a larger class of grid subgraphs $H$ obtained via a recursive blowup procedure satisfies $\mathrm{gr}(H,K_k)=k^{O_H(1)}$. Finally, we show that conditional on the multicolor Erdős-Hajnal conjecture, $\mathrm{gr}(H,K_k)=k^{O_H(1)}$ for any $H$ with two rows that does not contain $G_{2\times 2}$.

15 pages, 6 figures