  The group synchronization problem is to estimate unknown group elements at
the vertices of a graph when given a set of possibly noisy observations of
group differences at the edges. We consider the group synchronization problem
on finite graphs with size tending to infinity, and we focus on the question of
whether the true edge differences can be exactly recovered from the
observations (i.e., strong recovery). We prove two main results, one positive
and one negative. In the positive direction, we prove that for a sequence of
synchronization problems containing the complete digraph along with a
relatively well behaved prior distribution and observation kernel, with high
probability we can recover the correct edge labeling. Our negative result
provides conditions on a sequence of sparse graphs under which it is impossible
to recover the correct edge labeling with high probability.
