# Testing triangular properties (1/2)

septembre, 19, 2009
Sylvain

A few years ago, I worked together with Yves Verhoeven on the problem of testing triangular properties. We did some proofs, wrote a few pages but decided not to publish our work (since it is far from being optimal, and also far from being really interesting). However I think that this is worth a few lines in this blog. It is clearly more technical than the average post of my blog, so don’t force yourself into reading it.

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 if a set violates a triangular property.

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.

Let us now fix a triangular property $P$.

Lemma 1
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$.

Proof
When one removes one element from $V$, it removes $n-1$ edges from $E$. When one removes a second element, it then removes an extra $n-2$ edges, and so on… So that when one removes $\kappa$ elements, one removes $\sum_{i=1}^\kappa (n-i)$ edges form the graph, which is smaller than $\kappa(n-1)$. As we want to remove at least $\epsilon\cdot n^2$ edges, this leads to the following inequality

$\kappa\geq \epsilon\frac{n^2}{n-1},$

which implies $\kappa\geq \epsilon\cdot n$.

Lemma 2
Suppose that there exists a $B$ like in lemma 1.
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$.

Proof
Let us construct such a family $C$. Suppose, without loss of generality, that $B$ is minimal (with respect to the cardinality).

In order to construct $C$, we use the following greedy algorithm.

Input: a complete graph $K_n=(V,E)$ and a minimal set $B$ such that $\phi_{|V-B}$ has property $P$
Output: a family $C$ of independent bad triangles

1. $G:=K_n$.
2. $C:=\emptyset$.
3. $\mathsf{Bad}:=B$.
4. WHILE there exists a bad triangle $\{a,b,c\}$ such that $a\in\mathsf{Bad}$ and $b,c\in V_G-\mathsf{Bad}$
1. pick such a triangle.
2. restrict $G$ to $V_G-\{a,b,c\}$.
3. $\mathsf{Bad}:=\mathsf{Bad}\cap V_G$.
4. add the triangle $\{a,b,c\}$ to $C$.
5. return $C$.

Firstly, observe that by construction the family $C$ is made of independent triangles.

Now it remains to be proved that the second announced property holds, as we already know from the previous lemma that $|B|\geq\epsilon n$. Suppose this is not the case, that is $|C|<\lfloor|B|/3\rfloor$. Using this we will construct a set $B’$ verifying the same constraints as $B$, and such that $|B’|<|B|$, thus contradicting the minimality of $B$.

The fact that the algorithm stops comes from the fact that $G$ does not contain any bad triangle any more, so that $B’=V-V_G$ satisfies the same conditions as $B$. Let us examine the size of $B’$:

$|B’|=|V|-|V_G| = |V|-(|V|-3\cdot |C|) = 3\cdot |C| < 3\cdot \lfloor\frac{|B|}{3}\rfloor = |B|$

This concludes the proof.

We can now jump to the probabilistic part of our work. For a given family of triangles $C$, we denote by $\hat{C}$ the union of the triangles in $C$.

Lemma 3
Let $C$ be a family of triangles as defined in lemma 2. If one randomly picks $\Theta(|C|^{2/3})$ elements from $\hat{C}$ then he gets at least one complete triangle in $C$ with a probability lower-bounded by a nonzero constant as $n$ goes to infinity.

I am pretty sure that you want the rest of this work as soon as possible (really, uh?), I will do as fast as I can to put the proof of lemma 3 and the remaining…

### 3 Responses to “Testing triangular properties (1/2)”

Haha, now I’m waiting for the following… I should notice it was only part 1 before reading 🙁
I just found a typo in the definition: « two triangleS »

johan, 13 octobre 2009 à 14:25

You got me! Typo fixed…

Sylvain, 9 novembre 2009 à 7:20
Picture: courtesy of Abby Blank