  We study the Potts spin glass model, which generalizes the
Sherrington-Kirkpatrick model to the case when spins take more than two values
but their interactions are counted only if the spins are equal. We obtain the
analogue of the Parisi variational formula for the free energy, with the order
parameter now given by a monotone path in the set of positive-semidefinite
matrices. The main idea of the paper is a novel synchronization mechanism for
blocks of overlaps. This mechanism can be used to solve a more general version
of the Sherrington-Kirkpatrick model with vector spins interacting through
their scalar product, which includes the Potts spin glass as a special case. As
another example of application, one can show that Talagrand's bound for
multiple copies of the mixed $p$-spin model with constrained overlaps is
asymptotically sharp. We consider these problems in the subsequent paper,
arXiv:1512.04441, and illustrate the main new idea on the technically more
transparent case of the Potts spin glass.
