# Property testing of triangular properties

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 ?

-
Could you give an example of triangular property? – Mohammad Al-Turkistany Sep 14 '10 at 21:51
The triangle inequality was our target at that time. – Sylvain Peyronnet Sep 15 '10 at 8:43

Your problem is well-understood in the case $S = \{0,1\}$. Here, the function $\phi$ can be viewed as the adjacency matrix of a graph $G_\phi$ on the vertex set $V$. And $\phi$ satisfying a triangular property $P$ just means that $G_\phi$ is free of some collection $C_P$ of induced subgraphs, each on $3$ vertices. Now, it is known [Alon-Fischer-Krivelevich-Szegedy '99] that any such property is testable (in the property testing sense) with query complexity, independent of $n$, bounded from above by a tower of exponentials of height polynomial in $1/\epsilon$. In particular, when $P$ is 1 only when its input is $(1,1,1)$, the property corresponds to triangle-freeness in graphs for which the best upper-bound is the tower of exp's I mentioned and the best lower bound is slightly superpolynomial in $1/\epsilon$ [Alon '01]. If you want better dependence on $1/\epsilon$ at the cost of perhaps having some dependence on $n$, I don't believe anything much better than what you described is known. The test you described is more or less folklore.
For arbitrary fixed $S$, I don't know if the testability question has been resolved. I believe the framework of graph limits, especially the paper [Borgs-Chayes-Lovász-Sos-Szegedy-Vesztergombi '06], might show testability for hereditary properties of weighted graphs which would imply testability of your triangle properties. But I don't know this fact for sure.
I am aware of the result for $S=\{0,1\}$ but fail to find a generalization to weighted graphs. I will check the paper of Borgs et al. Thanks ! – Sylvain Peyronnet Sep 15 '10 at 8:41
Welcome! I'll also try to find out more about whether Borgs et al. implies anything for weighted graph properties. Btw, as I mentioned, even for $S = \{0,1\}$, question of getting milder dependency on $\epsilon$ while having sublinear dependency on $n$ is wide open. – arnab Sep 15 '10 at 10:22