I'm asked to use the following lemma to prove the statement below.
Theorem 1.1.1 (Triangle Removal Lemma). For every $\gamma>0$ there exists $\delta=\delta(\gamma)>0$ such that for every graph $G$ at least one of the following is true.
(A) there exists $F \subseteq E(G),|F| \leq \gamma v(G)^{2}$, such that $G-F$ is triangle-free
(B) $G$ contains at least $\delta v(G)^{3}$ triangles
A graph $G$ is called $\epsilon$-far from being triangle-free, if the removal of $\epsilon v(G)^{2}$ edges does not make $G$ triangle-free.
Prove that there exists a function $f: \mathbb{R}_{\geq 0} \mapsto \mathbb{N}$ and a randomized algorithm $\mathcal{A}$ that takes an input a graph $G$ and a (tolerance) parameter $\epsilon>0$, queries at most $f(\varepsilon)$ pairs of $V(G)$ (whether they are an edge of $G$ ) and outputs either accept or reject, such that
- if $G$ is triangle-free, then $\mathcal{A}$ outputs accept with probability 1 ,
- if $G$ is $\epsilon$-far from triangle free, then $\mathcal{A}$ outputs reject with probability $0.9999 .$
I only have a vague idea of what $\mathcal{A}$ should do. Given an input graph $G$ on $n$ vertices, $\mathcal{A}$ would check some $x$ number of triples of vertices of $G$ uniformly at random ($x$ to be determined), and see if they form a triangle. If they do, then $\mathcal{A}$ rejects it. Otherwise $\mathcal{A}$ accepts the graph.
If $G$ is triangle-free, then there is no triangles for $\mathcal{A}$ to reject, and so $G$ would be accepted with probability $1$, as required.
Otherwise, if $G$ is $\epsilon$-far from being triangle-free, the lemma implies that $G$ has at least $\delta n^3$ triangles, for some $\delta = \delta(\epsilon) > 0$. So, given an $\epsilon > 0$, we have a constant number of queries $f(\epsilon)$, and we must somehow determine if $G$ is $\epsilon$-far from being triangle-free $99.99\%$ of the time, even when the number of triangles grows at the rate of $\delta n^3$ as $n$ increases, where $\delta$ is also given by $\epsilon$.
I'm guessing that there is a pattern to the distribution of the triangles in $G$, which I'd need to uncover. If this is true, we might be able to choose an appropriate value for $f(\epsilon)$, and sample the triples of vertices in a certain way according to the distribution of triangles. Before proceeding, I'd like to ask for some comments on this approach, and some hints on which statements to prove next to solve this problem.
Given $\epsilon > 0$, let $\delta = \delta(\epsilon)$ as in the Triangle Removal Lemma. Let $m$ be a constant to be determined later. Algorithm $\mathcal{A}$ picks $m / \delta$ triplets in $G$ independently, uniformly at random, and accepts $G$ as triangle-free if none of the chosen triplets forms a triangle, and rejects otherwise. If $G$ is $\epsilon$-far from triangle-free, then by TRL, at least $\delta n^3$ triangles exist. Therefore, every time we sample a triplet, it forms a triangle with probability at least $$\delta n^3 / \binom{n}{3} \geq 6\delta$$ Algorithm $\mathcal{A}$ fails to choose any of those triangles with probability at most $$(1 - 6\delta)^{m/\delta} \leq e^{-6m}.$$ We may choose $m$ large enough so that $e^{-6m} \leq 0.0001$.