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

$G:=K_n$ .
$C:=\emptyset$ .
$\mathsf{Bad}:=B$ .
WHILE there exists a bad triangle such that and
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$ .
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…

Algorithms and computation, Level 3 | Comments (RSS) | 3 comments »

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

Testing triangular properties (1/2)

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

Catégories

Blogoliste

Archives