Abundance: Asymmetric Graph Removal Lemmas and Integer Solutions to Linear Equations

Abstract

We prove that a large family of pairs of graphs satisfy a polynomial dependence in asymmetric graph removal lemmas. In particular, we give an unexpected answer to a question of Gishboliner, Shapira, and Wigderson by showing that for every $t⩾4$, there are $K_t$-abundant graphs of chromatic number $t$. Using similar methods, we also extend work of Ruzsa by proving that a set $\mathcal{A}\subset \{1,\dots ,N\}$ which avoids solutions with distinct integers to an equation of genus at least two has size $\mathcal{O}(\sqrt{N})$. The best previous bound was $N^{1-o(1)}$ and the exponent of $1/2$ is best possible in such a result. Finally, we investigate the relationship between polynomial dependencies in asymmetric removal lemmas and the problem of avoiding integer solutions to equations. The results suggest a potentially deep correspondence. Many open questions remain.

28 pages, 4 figures