Testing triangular properties (1/2)

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 $latex K_n=(V,E)$ be the complete graph on $latex n$ vertices and $latex S$ be a set. Let $latex \phi:V\times V\rightarrow S$ be a function, and let $latex 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 $latex P$ is a function $latex P:S^3\rightarrow\{0,1\}$ that is invariant under permutations. The function $latex \phi$ is said to have the property $latex P$ if for all triangles $latex \{a,b,c\}$ the value $latex P(\phi(a,b),\phi(b,c),\phi(c,a))$ is equal to $latex 1$. The function $latex \phi$ is said to be at least $latex \epsilon$-far from having property $latex P$ if for all function $latex \psi:V\times V\rightarrow S$ having the property $latex P$ the functions $latex \phi$ and $latex \psi$ differ on at least $latex \epsilon\cdot n^2$ values.
Two triangles are said to be independent if their intersection is empty.
A triangle $latex v$ is said to be bad (with respect to $latex P$) if $latex P$ takes the value $latex 0$ on it.

Let us now fix a triangular property $latex P$.

Lemma 1
Suppose that $latex \phi$ is $latex \epsilon$-far from having property $latex P$. Let $latex B$ be a set of vertices so that $latex \phi$ induces a function that has property $latex P$ on the restriction of $latex K_n$ to $latex V-B$. Then the cardinality of $latex B$ is greater than $latex \epsilon\cdot n$.

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

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

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

Lemma 2
Suppose that there exists a $latex B$ like in lemma 1.
There exists a family $latex C$ of independent triangles in $latex K_n$ such that

• each triangle in $latex C$ is bad,

• $latex |C|\geq\lfloor\frac{|B|}{3}\rfloor\geq \frac{\epsilon\cdot n}{3}-1$.

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

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

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

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

Firstly, observe that by construction the family $latex 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 $latex |B|\geq\epsilon n$. Suppose this is not the case, that is $latex |C|<\lfloor|B|/3\rfloor$. Using this we will construct a set $latex B’$ verifying the same constraints as $latex B$, and such that $latex |B’|<|B|$, thus contradicting the minimality of $latex B$.

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

$latex |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 $latex C$, we denote by $latex \hat{C}$ the union of the triangles in $latex C$.

Lemma 3
Let $latex C$ be a family of triangles as defined in lemma 2. If one randomly picks $latex \Theta(|C|^{2/3})$ elements from $latex \hat{C}$ then he gets at least one complete triangle in $latex C$ with a probability lower-bounded by a nonzero constant as $latex 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…