Testing triangular properties (1/2)

septembre, 19, 2009

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.

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.

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.

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