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

Jacob Fox (Department of Mathematics, Stanford University, Stanford, California, U.S.A.)

Sammy Luo (Department of Mathematics, Stanford University, Stanford, California, U.S.A.)

Yuval Wigderson (Department of Mathematics, Stanford University, Stanford, California, U.S.A.)

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

Received 18 December 2019

Accepted 9 March 2020

Published 4 January 2021