<p>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 <a href="http://www.tau.ac.il/~nogaa/PDFS/testn12.pdf">[Alon-Fischer-Krivelevich-Szegedy '99]</a> 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$ <a href="http://www.tau.ac.il/~nogaa/PDFS/testsubproc.pdf">[Alon '01]</a>.  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.</p>

<p>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 <a href="http://research.microsoft.com/en-us/um/people/jchayes/Papers/TestStoc.pdf">[Borgs-Chayes-Lovász-Sos-Szegedy-Vesztergombi '06]</a>, 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.</p>

CC BY-SA 2.5
2010-09-15T08:41:27.197Z
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
CC BY-SA 2.5
2010-09-15T10:22:19.323Z
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
CC BY-SA 2.5
2010-09-15T01:17:14.743Z
2010-09-15T02:14:29.837Z
2010-09-15T02:14:29.837Z
arnab
<p>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 <strong>I am asking if a better result is known, or if you have some ideas about the problem</strong>.</p>

<p>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.</p>

<p>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.</p>

<p><strong>definition</strong><br>
A triangular property $P$ is a function $P:S^3\rightarrow{0,1}$ that is invariant under permutations.<br>
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.<br>
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.<br>
Two triangles are said to be independent if their intersection is empty.<br>
A triangle $v$ is said to be bad (with respect to $P$) if $P$ takes the value 0 on it.</p>

<p>Our result is a property tester for triangular properties :</p>

<p><strong>Input</strong>: a function $\phi:V\times V \rightarrow S$ and a triangular property $P$.<br>
<strong>Output</strong>: the answer to whether or not $\phi$ is $\epsilon$-far from having property $P$.</p>

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

<p>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:</p>

<p>The technical result:<br>
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$.<br>
Using a $B$ as defined before, There exists a family $C$ of independent triangles in $K_n$ such that<br>
- each triangle in $C$ is bad,<br>
- $|C|\geq\lfloor\frac{|B|}{3}\rfloor\geq \frac{\epsilon\cdot n}{3}-1$.</p>

<p>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.<br>
Since we have a bad lower bound on $|C|$, we cannot obtain an interesting complexity for the tester...</p>

<p>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 ?</p>

CC BY-SA 2.5
2010-09-14T21:51:38.350Z
Could you give an example of triangular property?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-15T08:43:15.073Z
The triangle inequality was our target at that time.
Sylvain Peyronnet
<property-testing>
Property testing of triangular properties
Sylvain Peyronnet
# Property testing of triangular properties

(Asked by: username_0 on 2010-09-14)

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 ?

**Tags:** property-testing
> **Comments:**
> **username_1**: Could you give an example of triangular property?  
> **username_0**: The triangle inequality was our target at that time.  

---

## 1 answers

### Answer by username_2 on 2010-09-15. Score: 9 | Accepted answer

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]](http://www.tau.ac.il/~nogaa/PDFS/testn12.pdf) 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]](http://www.tau.ac.il/~nogaa/PDFS/testsubproc.pdf). 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]](http://research.microsoft.com/en-us/um/people/jchayes/Papers/TestStoc.pdf), 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.

> **Comments:**
> **username_0**: 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 !  
> **username_2**: 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.  

---

