  What is the probability that the number of triangles in $\mathcal{G}_{n,p}$,
the Erd\H{o}s-R\'enyi random graph with edge density $p$, is at least twice its
mean? Writing it as $\exp[- r(n,p)]$, already the order of the rate function
$r(n,p)$ was a longstanding open problem when $p=o(1)$, finally settled in 2012
by Chatterjee and by DeMarco and Kahn, who independently showed that
$r(n,p)\asymp n^2p^2 \log (1/p)$ for $p \gtrsim \frac{\log n}n$; the exact
asymptotics of $r(n,p)$ remained unknown.
  The following variational problem can be related to this large deviation
question at $p\gtrsim \frac{\log n}n$: for $\delta>0$ fixed, what is the
minimum asymptotic $p$-relative entropy of a weighted graph on $n$ vertices
with triangle density at least $(1+\delta)p^3$? A beautiful large deviation
framework of Chatterjee and Varadhan (2011) reduces upper tails for triangles
to a limiting version of this problem for fixed $p$. A very recent breakthrough
of Chatterjee and Dembo extended its validity to $n^{-\alpha}\ll p \ll 1$ for
an explicit $\alpha>0$, and plausibly it holds in all of the above sparse
regime.
  In this note we show that the solution to the variational problem is
$\min\{\frac12 \delta^{2/3}\,,\, \frac13 \delta\}$ when $n^{-1/2}\ll p \ll 1$
vs. $\frac12 \delta^{2/3}$ when $n^{-1} \ll p\ll n^{-1/2}$ (the transition
between these regimes is expressed in the count of triangles minus an edge in
the minimizer). From the results of Chatterjee and Dembo, this shows for
instance that the probability that $\mathcal{G}_{n,p}$ for $ n^{-\alpha} \leq p
\ll 1$ has twice as many triangles as its expectation is $\exp[-r(n,p)]$ where
$r(n,p)\sim \frac13 n^2 p^2\log(1/p)$. Our results further extend to
$k$-cliques for any fixed $k$, as well as give the order of the upper tail rate
function for an arbitrary fixed subgraph when $p\geq n^{-\alpha}$.
