Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
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
add comment

1 Answer

up vote 9 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.