__
TR01-049 | 11th July 2001 00:00
__

#### On Multi-Partition Communication Complexity of Triangle-Freeness

**Abstract:**
We show that recognizing the $K_3$-freeness and $K_4$-freeness of

graphs is hard, respectively, for two-player nondeterministic

communication protocols with exponentially many partitions and for

nondeterministic (syntactic) read-$s$ times branching programs.

The key ingradient is a generalization of a coloring lemma, due to

Papadimitriou and Sipser, which says that for every balanced

red-blue coloring of the edges of the complete $n$-vertex graph

there is a set of $cn^2$ triangles, none of which is

monochromatic and no triangle can be formed by picking edges

from different triangles.

Using a probabilistic argument, we extend this lemma to the case

of exponentially many colorings as well as to partial colorings.

__
Comment #1 to TR01-049 | 25th July 2002 17:28
__
#### Triangle-Freeness is Also Hard for Read-r Times Branching Programs Comment on: TR01-049

**Abstract:**
In ECCC TR01-049 we have proved a truly exponential lower bound

on the size of r-n.b.p. (nondeterministic syntacticcread-r times

branching program) recognizing whether a given graph has no

4-clique. Here we note that, although not explicitely stated there,

the same argument implies a (not truly but still exponential)

lower bound also for r-b.p.'s recognizing the triangle-freeness

of graphs.