Removal lemmas and approximate homomorphisms

Abstract

We study quantitative relationships between the triangle removal lemma and several of its variants. One such variant, which we call the triangle-free lemma, states that for each $\epsilon >0$ there exists $M$ such that every triangle-free graph $G$ has an $\epsilon$-approximate homomorphism to a triangle-free graph $F$ on at most $M$ vertices (here an $\epsilon$-approximate homomorphism is a map $V(G)\to V(F)$ where all but at most $\epsilon |V(G){|}^2$ edges of $G$ are mapped to edges of $F$). One consequence of our results is that the least possible $M$ in the triangle-free lemma grows faster than exponential in any polynomial in ${\epsilon }^{-1}$. We also prove more general results for arbitrary graphs, as well as arithmetic analogues over finite fields, where the bounds are close to optimal.

16 pages, 2 figures

References in corpus (7)

• Progression-free sets in Z_4^n are exponentially small
• On cap sets and the group-theoretic approach to matrix multiplication
• Hypergraph regularity and the multidimensional Szemerédi theorem
• A distribution on triples with maximum entropy marginal
• A lower bound for the $k$-multicolored sum-free problem in ${\mathbb{Z}}_m^n$
• Larger Corner-Free Sets from Better NOF Exactly-$N$ Protocols
• Lower bounds for corner-free sets