Finding blowups one vertex at a time

Abstract

An influential theorem of Nikiforov states that if an $N$-vertex graph $G$ contains at least ${\hat{I}}^3{N}^h$ copies of some fixed $h$-vertex graph $H$, then $G$ contains an $H$-blowup of order $c_H({\hat{I}}^3)\log N$. We provide a new proof of this theorem, which in particular improves the best known bound on the constant $c_H({\hat{I}}^3)$. In contrast to previous proofs, our proof is iterative, finding the blowup one vertex at a time.

20 pages