Testing triangular properties (2/2)

To find the beginning of the triangular adventure, you should read this post.

To prove the lemma we use the following theorem that I am not proving in this post (if you want the proof, just let me know).

Theorem
Consider $latex N$ urns each filled with $latex m$ balls, and the following process: pick a ball in an urn chosen uniformly at random until the chosen urn is empty. The probability that one had to pick more than $latex O(N^{\frac{m-1}{m}})$ balls tends to a nonzero constant as $latex N$ goes to infinity.

Proof (of the lemma)
To each triangle in $latex C$ associate an urn, filled with $latex 3$ balls labeled with the vertices of the triangle corresponding to the urn in which they are put. It is clear that if one applies the process described in the theorem above then in time $latex \Theta(|C|^{2/3})$ one will have picked the three balls of an urn with constant probability, and the labels of these balls form a triangle in $latex C$.

Now we can characterize the number of elements that must be pick at random in order to obtain a complete triangle (since we cannot directly sample triangles but only atomic elements). The following lemma gives the result.

Lemma
Let $latex C$ be a family of triangles as defined in one of the previous lemma.
If one picks $latex \Theta(\epsilon^{-1/3}n^{2/3})$ different elements in $latex V$ uniformly at random, then one has picked a complete triangle in $latex C$ with a probability that tends to a constant as $latex n$ goes to infinity.

Proof
Let $latex N=k\epsilon^{-1/3}n^{2/3}$ where $latex k$ is a constant, and suppose $latex (X_i)_{1\leq i\leq N}$ is a family of random variables such that $latex X_i$ is chosen uniformly at random in $latex V-\{X_1,\ldots,X_{i-1}\}$. The variable $latex X_i$ takes its value inside $latex \hat{C}$ with probability $latex \frac{|\hat{C}-\{X_1,\ldots,X_{i-1}|\}}{|V|}$ which is greater than

$latex \frac{|\hat{C}|-N}{|V|} \geq \frac{\epsilon n-N}{n} \geq \epsilon – k(\epsilon n)^{-1/3}$.

where the first inequality comes from one of our lemmas.
So, the expectation of the number $latex N_C$ of elements chosen in $latex \hat{C}$ is lower-bounded as follows:

$latex \exp[N_C]\geq N\cdot(\epsilon – k(\epsilon n)^{-1/3})=k(\epsilon n)^{2/3}-k^2(\epsilon n)^{1/3}.$

Then, using the Chernoff bound (see for instance the book by Motwani and Raghavan) we obtain

$latex Prob[N_C<\frac{k(\epsilon n)^{2/3}}{2}]\leq Prob[N_C<\frac{\exp[N_C]+k(\epsilon n)^{1/3}}{2}]$

$latex Prob[N_C<\frac{k(\epsilon n)^{2/3}}{2}] \leq prob[N_C<\exp[N_C](1-\frac{1}{2}+\frac{k(\epsilon n)^{1/3}}{2\exp[N_C]})]$

$latex Prob[N_C<\frac{k(\epsilon n)^{2/3}}{2}] \leq prob[N_C<\exp[N_C](1-\frac{1}{2}+\frac{k(\epsilon n)^{1/3}}{2\exp[N_C]})]$

$latex Prob[N_C<\frac{k(\epsilon n)^{2/3}}{2}] < e^{-\frac{1}{2}\exp[N_C]\cdot(\frac{1}{2}-\frac{k(\epsilon n)^{1/3}}{2\exp[N_C]})^2}$

But from one of the previous equation it follows that $latex (\frac{1}{2}-\frac{k(\epsilon n)^{1/3}}{2\exp[N_C]})^2$ tends to $latex 1/2$ as $latex n$ goes to infinity, implying that $latex Prob[N_C<k(\epsilon n)^{2/3}/2]$ tends to $latex 0$ as $latex n$ goes to infinity.

One shoud notice that $latex k(\epsilon n)^{2/3}/2=\Theta(|C|^{2/3})$, so that with with high-probability one can apply the previous lemma as $latex N_C\geq k(\epsilon n)^{2/3}/2$, which concludes the proof.

At last, we have now our final result…

Proposition
The following algorithm is a one-sided $latex \epsilon$-tester for any triangular property $latex P$, which requests $latex O(\epsilon^{-2/3}n^{4/3})$ values of the function $latex \phi$ that is to be tested.

The algorithm
$latex \epsilon$-tester for any triangular property
Input: a function $latex \phi:V\times V \rightarrow S$ and a triangular property $latex P$.
Output: the answer to whether or not $latex \phi$ is $latex \epsilon$-far from having property $latex P$.

• Select a random set of vertices $latex V’$ of size $latex \epsilon^{-1/3}n^{2/3}$.
• Request all the values of the restriction of $latex \phi$ to the complete graph $latex K_{\epsilon^{-1/3}n^{2/3}}$ induced by $latex V’$
• Check on all the triangles whether $latex P$ is satisfied or not.
• Return $latex 0$ if a triangle is bad, and $latex 1$ else.

The last thing to do? proving the proposition…

Proof
It is clear that if the function $latex \phi$ has property $latex P$ then it is also true for its restriction to the induced subgraph, so the algorithm accepts. If $latex \phi$ is $latex \epsilon$-far from having property $latex P$, then the first lemma implies the existence of a set $latex B$ which in turn implies the existence of a set $latex C$ as described in the second lemma. The third lemma then implies that with high probability the restriction of $latex \phi$ to the chosen subgraph will not have property $latex P$, which is exactly what is checked by the algorithm. So, The algorithm will reject with high probability. This concludes the proof.