Blowups of triangle-free graphs

The blowup of order $k$ of a graph $H$, denoted by $H[k]$, is the graph obtained from $H$ by replacing every vertex by an independent set of size $k$ and every edge $uv$ by a complete bipartite graph $K_{k,k}$ between the independent sets associated to $u$ and $v$. Blowups of graph naturally appear in many contexts in extremal graph theory: for instance, Turán graphs can be seen as blowups of complete graphs (under suitable divisibility conditions), and the Blowup lemma is a fundamental tool in combination with the Regularity lemma.

A classical result of Nikiforov asserts that whenever an $n$-vertex graph $G$ contains $\gamma n^h$ copies of a graph $H$ on $h$ vertices, then $G$ actually contains a blowup of $H$ of order $c(\gamma,H) \log n$. While the logarithmic dependence in $n$ is best possible, as shown by random graphs, the dependence in $\gamma$ is not well understood, except in degenerate cases (when $H$ is bipartite for instance). The best known lower bounds on $c(\gamma,H)$ were polynomial in $\gamma$. When $H$ is triangle-free, the present paper improves this to $c(\gamma,H)=c_H /\log(1/\gamma)$, for some constant $c_H$ that only depends on $H$. This is best possible, and in particular this implies that $G$ contains $H[k]$ already when $G$ contains $n^{h-c_H/k}$ copies of $H$. The new result has a number of interesting consequences such as an improved upper bound on the multicolor Ramsey number of blowups of triangle-free graphs.