  Contributing to the rigorous understanding of BP, in this paper we relate the
convergence of BP to spectral properties of the graph. This encompasses a
result for random graphs with a ``planted'' solution; thus, we obtain the first
rigorous result on BP for graph coloring in the case of a complex graphical
structure (as opposed to trees). In particular, the analysis shows how Belief
Propagation breaks the symmetry between the $3!$ possible permutations of the
color classes.
