2021/04/23 by Fox, Jacob, Zhao, Yufei
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2104.11626
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 ε>0 there exists M such that every triangle-free graph G has an ε-approximate homomorphism to a triangle-free graph F on at most M vertices (here an ε-approximate homomorphism is a map V(G) → V(F) where all but at most ε|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 ε-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.