Contents Online

# Journal of Combinatorics

## Volume 12 (2021)

### Number 1

### Extremal and Ramsey results on graph blowups

Pages: 1 – 15

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n1.a1

#### Authors

#### Abstract

Recently, Souza introduced blowup Ramsey numbers as a generalization of bipartite Ramsey numbers. For graphs $G$ and $H$, say $G \overset{r}{\to} H$ if every $r$-edge-coloring of $G$ contains a monochromatic copy of $H$. Let $H[t]$ denote the $t$-blowup of $H$. Then the blowup Ramsey number of $G$, $H$, $r$, and $t$ is defined as the minimum $n$ such that $G[n] \overset{r}{\to} H[t]$. Souza proved upper and lower bounds on $n$ that are exponential in $t$, and conjectured that the exponential constant does not depend on $G$. We prove that the dependence on $G$ in the exponential constant is indeed unnecessary, but conjecture that some dependence on $G$ is unavoidable.

An important step in both Souza’s proof and ours is a theorem of Nikiforov, which says that if a graph contains a constant fraction of the possible copies of $H$, then it contains a blowup of $H$ of logarithmic size. We also provide a new proof of this theorem with a better quantitative dependence.

#### Keywords

Ramsey theory, graph blowups

#### 2010 Mathematics Subject Classification

05C35, 05C55

The research of Jacob Fox was supported by a Packard Fellowship and by NSF award DMS-1855635.

The research of Sammy Luo and of Yuval Wigderson was supported by NSF GRFP Grant DGE-1656518.

Received 18 December 2019

Accepted 9 March 2020

Published 4 January 2021