  Over the past decade, physicists have developed deep but non-rigorous
techniques for studying phase transitions in discrete structures. Recently,
their ideas have been harnessed to obtain improved rigorous results on the
phase transitions in binary problems such as random $k$-SAT or $k$-NAESAT
(e.g., Coja-Oghlan and Panagiotou: STOC 2013). However, these rigorous
arguments, typically centered around the second moment method, do not extend
easily to problems where there are more than two possible values per variable.
The single most intensely studied example of such a problem is random graph
$k$-coloring. Here we develop a novel approach to the second moment method in
this problem. This new method, inspired by physics conjectures on the geometry
of the set of $k$-colorings, allows us to establish a substantially improved
lower bound on the $k$-colorability threshold. The new lower bound is within an
additive $2\ln 2+o_k(1)\approx 1.39$ of a simple first-moment upper bound and
within $2\ln 2-1+o_k(1)\approx 0.39$ of the physics conjecture. By comparison,
the best previous lower bound left a gap of about $2+\ln k$, unbounded in terms
of the number of colors [Achlioptas, Naor: STOC 2004].
