Several years ago I worked a few days with a collaborator on property testing of triangular property. We end up with a disappointing result that I am sharing here and for which I am asking if a better result is known, or if you have some ideas about the problem.
Let $K_n=(V,E)$ be the complete graph on $n$ vertices and $S$ be a set. Let $\phi:V\times V\rightarrow S$ be a function, and let $1>\epsilon>0$ be a real number.
We are interested in triangular properties, that is properties of triangles (sets of 3 items). Our final goal is to decide with high probability if a set violates "strongly" a triangular property (in the sense of the property testing.
definition
A triangular property $P$ is a function $P:S^3\rightarrow{0,1}$ that is invariant under permutations.
The function $\phi$ is said to have the property $P$ if for all triangles ${a,b,c}$ the value $P(\phi(a,b),\phi(b,c),\phi(c,a))$ is equal to 1.
The function $\phi$ is said to be at least $\epsilon$-far from having property $P$ if for all function $\psi:V\times V\rightarrow S$ having the property $P$ the functions $\phi$ and $\psi$ differ on at least $\epsilon\cdot n^2$ values.
Two triangles are said to be independent if their intersection is empty.
A triangle $v$ is said to be bad (with respect to $P$) if $P$ takes the value 0 on it.
Our result is a property tester for triangular properties :
Input: a function $\phi:V\times V \rightarrow S$ and a triangular property $P$.
Output: the answer to whether or not $\phi$ is $\epsilon$-far from having property $P$.
1) Select a random set of vertices $V'$ of size $\epsilon^{-1/3}n^{2/3}$.
2) Request all the values of the restriction of $\phi$ to the complete graph $K_{\epsilon^{-1/3}n^{2/3}}$ induced by $V'$
3) Check on all the triangles whether $P$ is satisfied or not.
4) Return 0 if a triangle is bad, and 1 otherwise.
How do we obtain this? the first step is a technical result that gives the proportion of disjoints triangles that violate $P$, then we use a probabilistic argument based on a balls and bins theorem, and the result follow. Clearly this algorithm is far from being optimal. The problem is in the technical result:
The technical result:
Suppose that $\phi$ is $\epsilon$-far from having property $P$. Let $B$ be a set of vertices so that $\phi$ induces a function that has property $P$ on the restriction of $K_n$ to $V-B$. Then the cardinality of $B$ is greater than $\epsilon\cdot n$.
Using a $B$ as defined before, There exists a family $C$ of independent triangles in $K_n$ such that
- each triangle in $C$ is bad,
- $|C|\geq\lfloor\frac{|B|}{3}\rfloor\geq \frac{\epsilon\cdot n}{3}-1$.
Clearly, the problem is that our lower bound on the size of $C$ is poor. It is a shame that we have no better bound since the bound on $B$ is great.
Since we have a bad lower bound on $|C|$, we cannot obtain an interesting complexity for the tester...
So, the question is : are you aware of a result on this problem ? And if not, have you got some better ideas that we have ?
