Blowup Ramsey numbers

Abstract

We study a generalisation of the bipartite Ramsey numbers to blowups of graphs. For a graph $G$, denote the $t$-blowup of $G$ by $G[t]$. We say that $G$ is $r$-Ramsey for $H$, and write $G\stackrel{r}{\to }H$, if every $r$-colouring of the edges of $G$ has a monochromatic copy of $H$. We show that if $G\stackrel{r}{\to }H$, then for all $t$, there exists $n$ such that $G[n]\stackrel{r}{\to }H[t]$. In fact, we provide exponential lower and upper bounds for the minimum $n$ with $G[n]\stackrel{r}{\to }H[t]$, and conjecture an upper bound of the form $c^t$, where $c$ depends on $H$ and $r$, but not on $G$. We also show that this conjecture holds for $G(n,p)$ with high probability, above the threshold for the event $G(n,p)\stackrel{r}{\to }H$.

17 pages