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