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 be the complete graph on
vertices and
be a set. Let
be a function, and let
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 is a function
that is invariant under permutations. The function
is said to have the property
if for all triangles
the value
is equal to
. The function
is said to be at least
-far from having property
if for all function
having the property
the functions
and
differ on at least
values.
Two triangles are said to be independent if their intersection is empty.
A triangle is said to be bad (with respect to
) if
takes the value
on it.
Let us now fix a triangular property .
Lemma 1
Suppose that is
-far from having property
. Let
be a set of vertices so that
induces a function that has property
on the restriction of
to
. Then the cardinality of
is greater than
.
Proof
When one removes one element from , it removes
edges from
. When one removes a second element, it then removes an extra
edges, and so on… So that when one removes
elements, one removes
edges form the graph, which is smaller than
. As we want to remove at least
edges, this leads to the following inequality
which implies .
Lemma 2
Suppose that there exists a like in lemma 1.
There exists a family of independent triangles in
such that
- each triangle in
is bad,
-
.
Proof
Let us construct such a family . Suppose, without loss of generality, that
is minimal (with respect to the cardinality).
In order to construct , we use the following greedy algorithm.
Input: a complete graph and a minimal set
such that
has property
Output: a family of independent bad triangles
.
-
.
-
.
- WHILE there exists a bad triangle
such that
and
- pick such a triangle.
- restrict
to
.
.
- add the triangle
to
.
- return
.
Firstly, observe that by construction the family 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 . Suppose this is not the case, that is
. Using this we will construct a set
verifying the same constraints as
, and such that
, thus contradicting the minimality of
.
The fact that the algorithm stops comes from the fact that does not contain any bad triangle any more, so that
satisfies the same conditions as
. Let us examine the size of
:
This concludes the proof.
We can now jump to the probabilistic part of our work. For a given family of triangles , we denote by
the union of the triangles in
.
Lemma 3
Let be a family of triangles as defined in lemma 2. If one randomly picks
elements from
then he gets at least one complete triangle in
with a probability lower-bounded by a nonzero constant as
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…