  The following question is due to Chatterjee and Varadhan (2011). Fix
$0<p<r<1$ and take $G\sim G(n,p)$, the Erd\H{o}s-R\'enyi random graph with edge
density $p$, conditioned to have at least as many triangles as the typical
$G(n,r)$. Is $G$ close in cut-distance to a typical $G(n,r)$? Via a beautiful
new framework for large deviation principles in $G(n,p)$, Chatterjee and
Varadhan gave bounds on the replica symmetric phase, the region of $(p,r)$
where the answer is positive. They further showed that for any small enough $p$
there are at least two phase transitions as $r$ varies.
  We settle this question by identifying the replica symmetric phase for
triangles and more generally for any fixed $d$-regular graph. By analyzing the
variational problem arising from the framework of Chatterjee and Varadhan we
show that the replica symmetry phase consists of all $(p,r)$ such that
$(r^d,h_p(r))$ lies on the convex minorant of $x\mapsto h_p(x^{1/d})$ where
$h_p$ is the rate function of a binomial with parameter $p$. In particular, the
answer for triangles involves $h_p(\sqrt{x})$ rather than the natural guess of
$h_p(x^{1/3})$ where symmetry was previously known. Analogous results are
obtained for linear hypergraphs as well as the setting where the largest
eigenvalue of $G\sim G(n,p)$ is conditioned to exceed the typical value of the
largest eigenvalue of $G(n,r)$. Building on the work of Chatterjee and Diaconis
(2012) we obtain additional results on a class of exponential random graphs
including a new range of parameters where symmetry breaking occurs. En route we
give a short alternative proof of a graph homomorphism inequality due to Kahn
(2001) and Galvin and Tetali (2004).
