On Multi-Partition Communication Complexity of Triangle-Freeness

Stasys Jukna and Georg Schnitger

Abstract. We show that recognizing the triangle-freeness and 4-clique-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.

Key Words: Edge colorings, expanders, triangle-free graphs, communication complexity, branching programs, lower bounds