% -*- mode: latex; TeX-PDF-mode: t; -*-
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.72}{25(1)}{2018}

%\setlength{\textwidth}{6.5in}
%\setlength{\textheight}{9in}
%\setlength{\topmargin}{-0.5in}
%\setlength{\oddsidemargin}{0in}
%\setlength{\evensidemargin}{0in}

\usepackage{diagbox}
\usepackage{mathtools}
\usepackage{bbm}
\usepackage{amsmath}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

%\usepackage{kbordermatrix}
%\renewcommand{\kbldelim}{(}% Left delimiter
%\renewcommand{\kbrdelim}{)}% Right delimiter
\allowdisplaybreaks

%there was some 'non-standard' mathtoolset directive here 
%which completely screws up all my equation references
%I have deleted it
\mathtoolsset{showonlyrefs}

\renewcommand{\emph}[1]{\textit{#1}}
\usepackage{enumerate,amsmath,amsthm,latexsym,amssymb}
\usepackage{color}\usepackage{graphicx}
%\usepackage{algpseudocode}


\def\tu{\tilde{u}}
\def\bal{\boldsymbol \alpha}
\def\bV{{V_\l}}
\definecolor{brown}{cmyk}{0, 0.72, 1, 0.45}
\definecolor{grey}{gray}{0.5}
%\newcommand{\gbs}[1]{{\blue #1}}
\newcommand{\dun}{\,\dot\cup\,}
\newcommand{\gbs}[1]{#1}
\def\blue{\color{blue}}
\def\green{\color{green}}
\def\cyan{\color{cyan}}
\def\magenta{\color{magenta}}
\def\brown{\color{brown}}
\def\black{\color{black}}
\def\yellow{\color{yellow}}
\def\grey{\color{grey}}
\def\red{\color{red}}
\def\bu{\bf u}
\def\leqa{\leq_a}
\def\dK{\vec{K}}
\newcommand{\old}[1]{}
\newcommand{\abs}[1]{\left|#1\right|}
\newcounter{rot}%\addtocounter{rot}{1}, \therot
\newcommand{\bignote}[1]{\vspace{0.25 in}\fbox{\parbox{6in}{\blue #1}}%
{\fbox{{\bf {\red \large Q \stepcounter{rot} \therot}}}}}

\newcommand{\AND}{\textnormal{ AND }}
\newcommand{\OR}{\textnormal{ OR }}

\newcommand{\card}[1]{\left|#1\right|}
\def\hr{\widehat{\rho}}
\newcommand{\ignore}[1]{}
\newcommand{\stack}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\def\bM{{\bf M}}
\newcommand{\M}[1]{M^{(#1)}}
\newcommand{\Gi}[1]{\Gamma^{(#1)}}
\def\cA{{\mathcal A}}
\def\cB{{\mathcal B}}
\def\cS{{\mathcal S}}
\def\cC{{\mathcal C}}
\def\cO{{\mathcal O}}
\def\hO{\widehat{\cO}}
\def\dD{{\vec D}}
\def\dE{\vec E}
\def\dG{\vec G}
\def\hcT{\hat{\cT}}
\def\inn{{\rm in}}
\def\out{{\rm out}}
\def\pee{{\mathcal P}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\ee}{\mathcal{E}}
\def\hc{\widehat{c}}

\def\cP{\mathcal{P}}
\def\cQ{\mathcal{Q}}
\newcommand{\gap}[1]{\mbox{\hspace{#1 in}}}
\newcommand{\prend}{\hspace*{\fill}\mbox{$\Box$}}
\newcommand{\prf}{\emph{Proof.  }}
\newcommand{\proofstart}{{\noindent \bf Proof\hspace{2em}}}
\newcommand{\proofend}{\hspace*{\fill}\mbox{$\Box$}\\ \medskip\\ \medskip}
\newcommand{\ratio}[2]{\mbox{$\frac{#1}{#2}$}}
\def\ii_(#1,#2){i_{#1}^{#2}}

\newcommand{\eqlabel}[1]{\parbox{3em}{\vspace{-\atopdisplayskip}%
\begin{equation} \label{#1}\end{equation}}}

\renewcommand{\S}[1]{S^{(#1)}}
\newcommand{\T}[1]{T^{(#1)}}
\newcommand{\hS}[1]{\hat{S}^{(#1)}}
\newcommand{\hT}[1]{\hat{T}^{(#1)}}
\def\qs{{\bf qs}}
\def\LL{\Lambda}
\newcommand{\lfrac}[2]{\left(\frac{#1}{#2}\right)}
\newcommand{\dee}{L_0}
\newcommand{\aand}{\mbox{ and }}
\def\bx{{\bf x}}
\def\hg{\hat{\g}}
\def\cM{\mathcal{M}}
\def\a{\alpha}
\def\b{\beta}
\def\d{\delta}
\def\D{\Delta}
\def\e{\varepsilon}
\def\f{\phi}
\def\F{\Phi}
\def\g{\gamma}
\def\G{\Gamma}
\def\k{\kappa}
\def\K{\Kappa}
\def\z{\zeta}
\def\h{\theta}
\def\th{\theta}
\def\Th{\Theta}
\def\l{\lambda}
\def\m{\mu}
\def\n{\nu}
\def\p{\pi}
\def\P{\Pi}
\def\r{\rho}
\def\R{\Rho}
\def\s{\sigma}
%\def\S{\Sigma}
\def\t{\tau}
\def\om{\omega}
\def\Om{\Omega}
\def\Up{\Upsilon}
\def\w{\omega}
\def\x{\xi}
\def\1{{\bf 1}}
\def\0{{\bf 0}}

\newcommand{\fmin}{\mathrm{fmin}}
\newcommand{\hit}{\mathrm{hit}}
\newcommand{\tem}{\mathrm{temp}}
\newcommand{\ttem}{\mathrm{ttemp}}

\newcommand{\blk}[3]{\mathrm{block}_{#1}^{#2}(#3)}
\newcommand{\vis}[2]{\mathrm{vis}_{#1}(#2)}
\newcommand{\se}[2]{\mathrm{see}_{#1}(#2)}
\newcommand{\visi}[3]{\mathrm{vis}_{#1}^{#2}(#3)}


\newcommand{\half}{\mbox{$\frac{1}{2}$}}

\newcommand{\mnote}[1]{\marginpar{{\red \footnotesize\raggedright#1}}}
\def\mstar{\mnote{****}}
\newcommand{\sfrac}[2]{{\scriptstyle {#1 \over #2} }}
\newcommand{\rdup}[1]{\left\lceil #1 \right\rceil}
\newcommand{\rdown}[1]{\mbox{$\left\lfloor #1 \right\rfloor$}}
\newcommand{\limninf}{\mbox{$\lim_{N \rightarrow \infty}$}}
\newcommand{\lf}{\lfloor}
\newcommand{\rf}{\rfloor}
\newcommand{\whp}{{\bf whp}\xspace}
\newcommand{\Whp}{{\bf Whp}\xspace}
\newcommand{\gi}{{\bf G}}
\newcommand{\ngi}{\overline{{\bf G}}}
\newcommand{\imp}{\Longrightarrow}
\newcommand{\ra}{\longrightarrow}
\newcommand{\rai}{\ra \infty}
\newcommand{\raz}{\ra 0}
\newcommand{\ooi}{(1+o(1))}
\newcommand{\Si}[2]{S_{#1}^{(#2)}}
\newcommand{\Sit}{S_i}
\newcommand{\Ti}[2]{T_{#1}^{(#2)}}
\newcommand{\Tit}{T_i}
\newcommand{\Ai}[2]{A_{#1}^{(#2)}}
\newcommand{\hSi}[2]{\hat{S}_{#1,\rho}^{(#2)}}
\newcommand{\hTi}[2]{\hat{T}_{#1,\rho}^{(#2)}}
\newcommand{\Kdir}{\vec{K}}
\newcommand{\Pois}{\operatorname{Pois}}

\newcommand{\pone}{\frac{\log n}{n}}
%\newcommand{\prob}{\mathbb{P}}

\def\bsa{{\boldsymbol \alpha}}
\def\cE{\mathcal{E}}
\def\cF{\mathcal{F}}
\def\cL{\mathcal{L}}
\def\cN{\mathcal{N}}
\def\cT{\mathcal{T}}
\def\prob{\Pr}
\def\Re{\mathbb{R}}
\def\Z{\mathbb{Z}}
\newcommand{\brac}[1]{\left( #1 \right)}

\newcommand{\bfm}[1]{\mbox{\boldmath $#1$}}
\newcommand{\ul}[1]{\mbox{\boldmath $#1$}}

\def\hx{\hat{x}}
\def\hy{\hat{y}}
\def\bn{\ul{n}}
\def\ulsi{\ul{\s}}
%\newcommand{\expect}{\operatorname{\bf E}}
\def\E{{\bf E}}
\def\Var{{\bf Var}}
\renewcommand{\Pr}{\operatorname{\bf Pr}}
\newcommand\bfrac[2]{\left(\frac{#1}{#2}\right)}
\def\cq{c_Q}
\def\dus{d(\ulsi)}
\def\bC{\bar{C}}
\def\hC{\hat{C}}

\newcommand{\ep}{\varepsilon}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{cons}[theorem]{Construction}
\newtheorem{remthm}[theorem]{Remark}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{remark}{\begin{remthm}\rm }{\end{remthm}}%
\newcounter{thmtemp}

\def\omk{\omega_{k,\e}}

\newenvironment{thmnum}[1]{
  \setcounter{thmtemp}{\value{theorem}}
  \setcounter{theorem}{#1}
  \addtocounter{theorem}{-1}
  \begin{theorem}
 }{
  \end{theorem}
  \setcounter{theorem}{\value{thmtemp}}
 }

% \newcommand{\ignore}[1]{}
\newcommand{\nospace}[1]{}

\def\Otilde{\operatorname{\tilde{O}}}
\def\path{\operatorname{PATH}}
\def\PD{\operatorname{PD}}
\def\END{\operatorname{END}}
\def\ATSP{\ensuremath{\operatorname{ATSP}}\xspace}
\def\AP{\ensuremath{\operatorname{AP}}\xspace}
\newcommand{\eqdef}{\doteq}

\newcommand{\al}{\alpha}
\newcommand{\chic}{\chi_{\mathrm{c}}}

\newcommand{\lo}{\ln}
\newcommand{\iS}{{i_S}}
\newcommand{\iT}{{i_T}}
\newcommand{\xs}{{x}}
\newcommand{\yt}{{y}}
\newcommand{\inunif}{\in_{\operatorname{unif}}}
\newcommand{\ubar}{\bar{u}}
\newcommand{\vbar}{\bar{v}}
\newcommand{\pinv}{\p^{-1}}
\newcommand{\eee}{\mathbb{E}}
\newcommand{\N}{\mathbb{N}}
\def\BDTS{\texttt{BDAPTA}}
\def\expdist{\ensuremath{\operatorname{Exp}}}
\def\EX{\expdist(1)}
\newcommand{\Bin}{\ensuremath{\operatorname{Bin}}}
\newcommand{\Be}{\ensuremath{\operatorname{Be}}}
\def\V{{\bf Var}}
\newcommand{\mult}[2]{\begin{multline}\label{#1}#2\end{multline}}
\newcommand{\beq}[2]{\begin{equation}\label{#1}#2\end{equation}}
\newcommand{\ZP}[1]{Z^{P}_{#1,n}}
\newcommand{\ZA}[1]{Z^{A}_{#1,n}}
\renewcommand{\Re}{\mathbb{R}}
\newcommand{\Xijk}{X_{i,j,k}\:}
\newcommand{\Cijk}{C_{i,j,k}}
\def\hX{\widehat{X}}
\def\hV{\widehat{V}}

%\parindent 0in
%\parskip .15in
\def\leb{\leq_b}
\def\geb{\geq_b}
\def\bA{{\bf A}}
\def\rank{\text{rank}}


\def\bX{{\bf X}}
\newcommand{\sbs}{\subset}
\newcommand{\stm}{\setminus}
\newcommand{\dist}{\mathrm{dist}}
\newcommand{\bbb}{\mathcal{B}}
\newcommand{\st}{\mid}
\def\bB{{\bf B}}
\def\bc{{\bf c}}
\def\hn{\widehat{n}}
\def\hm{\widehat{m}}
\def\bI{{\bf I}}
\def\br{{\bf r}}
\def\bL{{\bf L}}
\def\ba{{\bf a}}
\def\bR{{\bf R}}
\def\bC{{\bf C}}
\def\bY{{\bf Y}}
\def\bZ{{\bf Z}}
\def\bb{{\bf b}}
\def\bd{{\bf d}}
\def\GF{\mathbf{GF}}
\def\bt{{\boldsymbol \theta}}
\def\bhA{\widehat{\bA}}
\def\cU{\mathcal{U}}
\def\cUPP{\mathcal{UPP}}
\def\cLOW{\mathcal{LOW}}
\def\cX{{\cal X}}
\def\hd{\widehat{d}}
\def\hp{\widehat{p}}
\def\hG{\widehat{\G}}
\newcommand{\pw}{P_{\rm win}}
\newcommand{\pwo}{P_{\rm win1}}
\newcommand{\pwt}{P_{\rm win2}}
\newcommand{\powo}{P_{1\wedge\rm win 1}}
\newcommand{\ptwt}{P_{2\wedge\rm win2}}




\title{\bf Constraining the clustering transition for\\ colorings of sparse random graphs}
\author{Michael Anastos \quad\quad Alan Frieze\thanks{Research supported in part by NSF grant DMS1362785} \quad\quad Wesley Pegden\thanks{Research supported in part by NSF grant DMS1363136}\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Carnegie Mellon University\\[-0.8ex]
\small Pittsburgh PA 15213, U.S.A.} 

%% Added by CSG
\date{\dateline{May 23, 2017}{Mar 7, 2018}{Mar 29, 2018}\\
\small Mathematics Subject Classifications: 05C80}


\begin{document}
\maketitle

\begin{abstract}
Let $\Omega_q$ denote the set of proper $[q]$-colorings of the random graph $G_{n,m}, m=dn/2$ and let $H_q$ be the graph with vertex set $\Omega_q$ and an edge $\set{\s,\t}$ where $\s,\t$ are mappings $[n]\to[q]$ iff $h(\s,\t)=1$. Here $h(\s,\t)$ is the Hamming distance $|\set{v\in [n]:\s(v)\neq\t(v)}|$. We show that w.h.p. $H_q$ contains a single giant component containing almost all colorings in $\Omega_q$ if $d$ is sufficiently large and $q\geq \frac{cd}{\log d}$ for a constant $c>3/2$.

\bigskip\noindent \textbf{Keywords:} Random Graphs; Colorings; Clustering Transition
\end{abstract}

\section{Introduction}\label{intro}
In this short note, we will discuss a structural property of the set $\Omega_q$ of proper $[q]$-colorings of the random graph $G_{n,m}$, where $m=dn/2$ for some large constant $d$. That is, proper colorings using colors from $[q]=\set{1,2,\ldots,q}$. For the sake of precision, let us define $H_q$ to be the graph with vertex set $\Omega_q$ and an edge $\set{\s,\t}$ iff $h(\s,\t)=1$ where $h(\s,\t)$ is the Hamming distance $|\set{v\in [n]:\s(v)\neq\t(v)}|$. In the Statistical Physics literature the definition of $H_q$ may be that colorings $\s,\t$ are connected by an edge in $H_q$ whenever $h(\s,\t)=o(n)$. Our theorem holds a fortiori if this is the case.

Heuristic evidence in the statistical physics literature (see for example \cite{ZK}) suggests there is a \emph{clustering transition} $c_d$ such that for $q>c_d$, the graph $H_q$ is dominated by a single connected component, while for $q<c_d$, an exponential number of components are required to cover any constant fraction of it; it may be that $c_d\approx\frac{d}{\log d}$. (Here $A(d)\approx B(d)$ is taken to mean that $A(d)/B(d)\to 1$ as $d\to \infty$. We do not assume $d\to\infty$, only that $d$ is a sufficiently large constant, independent of $n$.)  Recall that $G_{n,m}$ for $m=dn/2$ becomes $q$-colorable around $q\approx\frac{d}{2\log d}$ or equivalently when $d\approx 2q\log q$, \cite{AN,CV}.
%
In this note, we prove the following:
\begin{theorem}\label{th1}
If $q\geq \frac{cd}{\log d}$ for constant $c>3/2$, and $d$ is sufficiently large, then w.h.p.~$H_q$ contains a giant component that contains almost all of $\Omega_q$.
\end{theorem}
 In particular, this implies that the clustering transition $c_d$, if it exists, must satisfy $c_d\leq \frac 3 2 \frac{d}{\log d}$.  

 Theorem \ref{th1} falls into the area of ``Structural Properties of Solutions to Random Constraint Satisfaction Problems''. This is a growing area with connections to Computer Science and Theoretical Physics.  In particular, much of the research on the graph $H_q$ has been focussed on the structure near the {\em colorability threshold}, e.g. Bapst, Coja-Oghlan, Hetterich, Rassman and Vilenchik \cite{BCHRV}, or the {\em clustering threshold}, e.g. Achlioptas, Coja-Oghlan and Ricci-Tersenghi \cite{ACR}, Molloy \cite{M}.  Other papers heuristically identify a sequence of phase transitions in the structure of $H_q$, e.g., Krz\c{a}kala, Montanari, Ricci-Tersenghi, Semerijan and Zdeborov\'a \cite{KMRSZ}, Zdeborov\'a and Krz\c{a}kala \cite{ZK}.  The existence of these transitions has been shown rigorously for some other CSPs. One of the most spectacular examples is due to Ding, Sly and Sun \cite{sly} who rigorously showed the existence of a sharp satisfiability threshold for random $k$-SAT.

An obvious target for future work is improving the constant in Theorem \ref{th1} to 1. We should note that Molloy \cite{M} has shown that w.h.p. there is no giant component if $q\leq \frac{(1-\e_d)d}{\log d}$, for some $\e_d>0$. Looking in another direction, it is shown in \cite{DFFV} that w.h.p. $H_q,q\geq d+2$ is connected. This implies that Glauber Dynamics on $\Omega_q$ is ergodic. It would be of interest to know if this is true for some $q\ll d$.

Before we begin our analysis, we briefly explain the constant 3/2. We start with an arbitrary  $[q]$-coloring and then re-color it using only approximately $\approx d/\log d$ of the given colors. We then use a disjoint set of approximately $d/2\log d$ colors to re-color it with a target $\chi\approx \frac{d}{2\log d}$ coloring $\t$. We will assume that $\t$ uses colors from $\set{q_0+1,\ldots,q_0+\chi}$.  
\section{Greedily Re-coloring}
Our main tool is a theorem from Bapst, Coja-Oghlan and Efthymiou \cite{BCE} on planted colorings. We consider two ways of generating a random coloring of a random graph. We will let $Z_q=|\Omega_q|$. The first method is to generate a random graph and then a random coloring. In the second method, we generate a random (planted) coloring and then generate a random graph compatible with this coloring.

\medskip
{\bf Random coloring of the random graph $G_{n,m}$:} Here we will assume that $m$ is such that w.h.p. $Z_q>0$.
\begin{enumerate}[(a)]
\item Generate $G_{n,m}$ subject to $Z_q>0$.
\item Choose a $[q]$-coloring $\s$ uniformly at random from $\Omega_q$.
\item Output $\Pi_1=(G_{n,m},\s)$.
\end{enumerate}
{\bf Planted model:} 
\begin{enumerate}
\item Choose a random partition of $[n]$ into $q$ color classes $V_1,V_2,\ldots,V_q$ subject to 
\beq{sizes}{
\sum_{i=1}^q\binom{|V_i|}{2}\leq \binom{n}{2}-m.
}
\item Let $\G_{\s,m}$ be obtained by adding $m$ random edges, each with endpoints in different color classes.
\item Output $\Pi_2=(\G_{\s,m},\s)$.
\end{enumerate}
We will use the following result from \cite{BCE}:
\begin{theorem}\label{plant}
Let $d=2m/n$ and suppose that $d\leq 2(q-1)\log(q-1)$. Then $\Pr(\P_2\in \cP)=o(1)$ implies that $\Pr(\P_1\in\cP)=o(1)$ for any graph+coloring property $\cP$.
\end{theorem}
Consequently, we will use the planted model in our subsequent analysis. Let
\beq{q0}{
q_0=\frac{q}{q-1}\cdot\frac{d}{\log d-7\log\log d}\approx \frac{d}{\log d}.
}
The property $\cP$ in question will be: ``the given $[q]$-coloring can be reduced via single vertex color changes to a $[q_0]$-coloring''.

In a random partition of $[n]$ into $q$ parts, the size of each part is distributed as $Bin(n,q^{-1})$ and so the Chernoff bounds imply that w.h.p. in a random partition each part has size $\frac{n}{q}\brac{1\pm \frac{\log n}{n^{1/2}}}$.

We let $\G$ be obtained by taking a random partition $V_1,V_2,\ldots,V_q$ and then adding $m=\frac12dn$ random edges so that each part is an independent set. These edges will be chosen from $$N_q=\binom{n}{2}-(1+o(1))q\binom{n/q}{2}=(1-o(1))\frac{n^2}{2}\brac{1-\frac1q}$$ 
possibilities. So, let $\hd=\frac{mn}{N_q}\approx\frac{dq}{q-1}$ and replace $\G$ by $\hG$ where each edge not contained in a $V_i$ is included independently with probability $\hp=\frac{\hd}{n}$. $V_1,V_2,\ldots,V_q$ constitutes a coloring which we will denote by $\s$. Now $\hG$ has $m$ edges with probability $\Omega(n^{-1/2})$ and one can check that the properties required in Lemmas \ref{indsparse0} and \ref{indsparse} below all occur with probability $1-o(n^{-1/2})$ and so we can equally well work with $\hG$.

Now consider the following algorithm for going from $\s$ via a path in $\Omega_q$ to a coloring with significantly fewer colors. It is basically the standard greedy coloring algorithm, as seen in Bollob\'as and Erd\H{o}s \cite{BE}, Grimmett and McDiarmid \cite{GM} and in particular Shamir and Upfal \cite{SU} for sparse graphs. 

In words, it goes as follows. At each round of the algorithm, $U$ denotes the set of vertices that have never been re-colored, by the start of the round. Having used $r-1$ colors to re-color some subset of vertices we start using color $r$. We let $W_j=V_j\cap U$ denote the unchanged vertices of $V_j$ for $j\geq 1$. We then let $k$ be the smallest index $j$ for which $W_j\neq\emptyset$.   During the re-coloring process, we will keep track of sets $C_r$ and $U_r\subseteq U$, which are, respectively, the sets of vertices already re-colored $r$ and the vertices of $U$ not adjacent to any vertices in $C_r$.   These sets are initially defined in the re-coloring process by the re-coloring all of $W_k$ with color $r$ so that $C_r=W_k$, and we proceed thereafter by choosing vertices from $U_r$ and re-coloring them with color $r$ (each time increasing $|C_r|$ by 1 and decreasing $|U_r|$ by at least 1).  We finish when $U_r=\emptyset$, and in this way the terminal set $C_r$ of vertices re-colored $r$ will be a maximal independent subset of the set $U$. Note that in this construction, some or all of the vertices in $V_r$ may be re-colored with $s<r$.

At any stage of the algorithm, $U$ is the set of vertices whose colors have not been altered. The value of $L$ in line D is $\rdup{n/\log^2\hd}$. 
\begin{tabbing}
{\sc algorithm greedy re-color}\\
{\bf beg}\={\bf in}\\
\>Initialise: $r=0,U=[n], C_0\gets \emptyset$;\=\\
\>{\bf repeat};\\
\>$r\gets$\=$r+1$, $C_r\gets\emptyset$;\\
\>\>Let $W_j=V_j\cap U$ for $j\geq 1$ and let $k=\min\set{j:W_j\neq \emptyset}$;\\
{\bf A:}\>\>$C_r\gets W_k,U\gets U\setminus C_r,U_r\gets U\setminus\set{\text{neighbors of $C_r$ in $\hG$}}$;\\
\>\>If $r<k$, re-color every vertex in $W_k$ with color $r$;\\
{\bf B:}\>\>{\bf rep}\={\bf eat} \=(Re-color some more vertices with color $r$);\\
{\bf C:}\>\>\>Arbitrarily choose $v\in U_r$, $C_r\gets C_r+v$, $U_r\gets U_r-v$;\\
\>\>\>$U_r\gets U_r\setminus\set{\text{neighbors of $v$ in $\hG$}}$;\\ 
\>\>{\bf until} $U_r=\emptyset$;\\
\>\>$U\gets U\setminus U_r$;\\
{\bf D:}\>{\bf until} $|U|\leq L$;\\
\>Suppose that at this point we have used $r_0$ colors;\\
\>If possible, re-color $U$ with colors $r_0+1,\ldots,r_0+s_0$, where $s_0=\rdup{\frac{\hd}{\log^2\hd}+2}$;\\
{\bf end}
\end{tabbing}
\subsection{Following a path in $H_q$}
We first observe that each re-coloring of a single vertex $v$ vertex in line C can be interpreted as moving from a coloring of $\Omega_q$ to a neighboring coloring in $H_q$. This requires us to argue that the re-coloring by {\sc greedy re-color} is such that the coloring of $\hG$ is proper at all times. We argue by induction on $r$ that the coloring at line A is proper. When $r=1$ there have been no re-colorings. At the start of round $r$ either all vertices previously colored $r$ have been re-colored and $C_r$ is a subset of vertices originally colored $k>r$ or is a subset of the vertices originally colored $r$. In the first case we can simply re-color $W_k$ one vertex at a time with color $r$. Also, during the loop beginning at line B we only re-color vertices with color $r$ if they are not neighbors of the set $C_r$ of vertices colored $r$ so far. This guarantees that the coloring remains proper until we reach line D. The following lemma shows that we can then reason as in Lemma 2 of Dyer, Flaxman, Frieze and Vigoda \cite{DFFV}, as will be explained subsequently. 
\begin{lemma}\label{indsparse0}
Let $p=m/\binom{n}{2}=\D/n$ where $\D$ is some sufficiently large constant.
With probability $1-o(n^{-1/2})$, every $S\subseteq [n]$ with $s=|S|\leq n/\log^2\D$ contains at most $s\D/\log^2\D$ edges. 
\end{lemma}
The above lemma, is Lemma 7.7(i) of  Janson, {\L}uczak and Ruci\'nski \cite{JLR} and it implies that if $\D=\hd$ then w.h.p. $\hG_U$  at line D contains no $K$-core, $K=\frac{2\hd}{\log^2\hd}+1$. Here $\hG_U$ denotes the sub-graph of $\hG$ induced by the vertices $U$. For a graph $G=(V,E)$ and $K\geq 0$, the $K$-core is the unique maximal set $S\subseteq V$ such that the induced subgraph on $S$ has minimum degree at least $K$. A graph without a $K$-core is {\em $K$-degenerate} i.e. its vertices can be ordered as $v_1,v_2,\ldots,v_n$ so that $v_i$ has at most $K-1$ neighbors in $\{v_1,v_2,\ldots,v_{i-1}\}$. To see this, let $v_n$ be a vertex of minimum degree and then apply induction.
 
Suppose now that we have reached Line D and we find $|U|\leq L$. We claim that we can re-color the vertices in $U$ with $K+1$ new colors, all the time following some path in $H_q$. Let $v_1,\dots,v_{|U|}$ denote an ordering of $U$ such that the degree of $v_i$ is less than $K$ in the subgraph $\hG_i$ of $\hG$ induced by $\{v_1,v_2,\dots,v_i\}$. We will prove the claim by induction on $i$, the inductive assertion being that we can re-color $v_1,v_2,\ldots,v_i$ ignoring conflicts caused by vertices $v_{i+1},\ldots,v_{|U|}$. The asertion with $i=|U|$ shows the existence of the path we want. The claim is trivial for $i=1$. Let $\s_0$ be the coloring of $U$ at line D, when first we have $|U|\leq L$. By induction there is a path $\s_0,\s_1,\ldots,\s_r$ from the coloring $\s_0$ restricted to $\hG_{i-1}$, using only colors $r_0+1,\ldots,r_0+s_0$ to do the re-coloring. Vertices outside of $U$ will not be re-colored by this sequence.

Let $(w_j,c_j)$ denote the $(vertex,color)$ change defining the edge $\set{\s_{j-1},\s_j}$.  We construct a path (of length $\leq 2r$) that re-colors $\hG_i$. For $j=1,2,\ldots,r$, we will re-color $w_j$ to color $c_j$, if no neighbor of $w_j$ has color $c_j$. Failing this, $v_i$ must be the only neighbor of $w_j$ that is colored $c_j$. This is because $\s_r$ is a proper coloring of $\hG_{i-1}$. Since $v_i$ has degree less than $K$ in $\hG_i$, there exists a new color for $v_i$ which does not appear in its neighborhood. Thus, we first re-color $v_i$ to any new (valid) color, and then we re-color $w_j$ to $c_j$, completing the inductive step. Note that because the colors used in Step D have not been used in Steps A,B,C, this re-coloring does not conflict with any of the coloring done in Steps A,B,C.
\subsection{Bounding the number of colors used}
We need to show that {\sc greedy re-color} uses at most $q_0$ colors. To do this we show that w.h.p. each execution of Loop B re-colors a large number of vertices. Let $\a_1(G)$ denote the minimum size of a {\em maximal} independent set of a graph $G$. The round will re-color at least $\a_1(\G_U)$ vertices, where $U$ is as at the start of Loop B. The following result is from Lemma 7.8(i) of \cite{JLR}.
\begin{lemma}\label{indsparse}
Let $p=m/\binom{n}{2}=\D/n$ where $\D$ is some sufficiently large constant.
Then $\a_1(G_{n,m})\geq \frac{\log \D-3\log\log \D}{p}$ with probability $1-o(n^{-1/2})$ (see Lemma 7.8(i)).
\end{lemma}
Now the application of Step A and Loop B re-colors a maximal independent set $C_r$ of the graph $\hG_U$ induced by $U$, as $U$ stands at the beginning of Step A.  This implies that the size of $C_r$ stochastically dominates the size of a maximal independent set in $G_{|U|,\hp}$. This is because we can obtain $G_{|U|,\hp}$ by adding edges to $V_i\cap U,i\geq 1$ with probability $\hp$. Here we follow the usual analysis of greedy algorithms and argue that edges inside $U$ are not conditioned by the process. This is often referred to as the method of deferred decisions. In this way we couple $\hG_U$ with $G_{|U|,\hp}$ so that every independent set in $G_{|U|,\hp}$ is contained in an independent set in $\hG_U$.

And so using Lemma \ref{indsparse} we see that w.h.p. each execution of Loop B re-colors at least 
$$\frac{\log(\hd/\log^2\hd)-3\log\log(\hd/\log^2\hd)}{\hd}n\geq \frac{q-1}{q} \cdot\frac{\log d-6\log\log d}{d}n$$ 
vertices, for $d$ sufficiently large. We have replaced $\D$ of Lemma \ref{indsparse} by $\hd/\log^2\hd$ to allow for the fact that we have replaced $n$ by $|U|\geq L$. Here we refer to the size of $|U|$ immediately after the update of $r$. Consequently, at the end of Algorithm {\sc greedy re-color} we will have used at most 

\beq{}{
\frac{q}{q-1}\cdot\frac{d}{\log d-6\log\log d}+\frac{\hd}{\log^2\hd}+2 \leq \frac{q}{q-1}\cdot\frac{d}{\log d-7\log\log d}=q_0
}
colors. The term $\frac{\hd}{\log^2\hd}+2$ arises from the re-coloring of $U$ at line D.

\subsection{Finishing the proof:} 
Now suppose that $q\geq \frac{cd}{\log d}$ where $d$ is large and $c>3/2$. Fix a particular $\chi$-coloring $\tau$ of $G_{n,m}$ that uses colors from $\set{q_0+1,\ldots,q_0+\chi}$. We prove that almost every $[q]$-coloring $\s$ of $G_{n,m}$ can be transformed into $\t$ changing one color at a time. It follows that for almost every pair of $[q]$-colorings $\s$, $\s'$ we can transform $\s$ into $\s'$ by first transforming $\s$ to $\t$ and then reversing the path from $\s'$ to $\t$.  

We proceed as follows. Applying Theorem \ref{plant} with the property $\cP$ as described following \eqref{q0}, we see that w.h.p., a uniformly random $[q]$-coloring $\s$ of $G_{n,m}$ can be transformed one vertex at a time into a $[q_0]$-coloring $\th$. Then we process the vertices of the color classes of $\t$, re-coloring vertices to their $\t$-color. When we process a color class $C$ of $\t$, we switch the color of vertices in $C$ to their $\t$-color $i_C$ one vertex at a time. We can do this because when we re-color a vertex $v$, a neighbor $w$ will currently either have one of the $q_0$ colors used by $\th$ and these are distinct from $i_C$ or alternatively, $w$ will have already been been re-colored with its $\t$-color and this will be distinct from $i_C$. This proves Theorem \ref{th1}.\qed

\subsection*{Acknowledgement} We thank the referee for an exemplary sequence of reviews.
\begin{thebibliography}{99}
\bibitem{AF}  D. Achlioptas and E. Friedgut, A Sharp Threshold for $k$-Colorability, {\em Random Structures and Algorithms}, 14 (1999) 63--70. 
\bibitem{ACR} D. Achlioptas, A. Coja-Oghlan and F. Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, {\em Random Structures and Algorithms} 38 (2010) 251--268.
\bibitem{AN} D. Achlioptas and A. Naor, The Two Possible Values of the Chromatic Number of a Random Graph, {\em Annals of Mathematics} 162 (2005) 1333--1349. 
\bibitem{BCHRV} V. Bapst, A. Coja-Oghlan, S. Hetterich, F. Rassmann and D. Vilenchik, The condensation phase transition in random graph coloring, {\em Communications in Mathematical Physics} 341 (2016) 543--606.
\bibitem{BCE} V. Bapst, A. Coja-Oghlan and C. Efthymiou, Planting colourings silently, {\em Combinatorics, Probability and Computing} 26 (2017) 338--366.
\bibitem{BE} B. Bollob\'as and P. Erd\H{o}s, Cliques in random graphs,
{\em Mathematical Proceedings of the Cambridge Philosophical Society} 80 (1976) 419--427.
\bibitem{CV} A. Coja-Oghlan and D. Vilenchik, Chasing the $k$-colorability threshold, {\em Proceedings of FOCS 2013}, 380--389.
\bibitem{sly} J. Ding, A. Sly and N. Sun, Proof of the satisfiability conjecture for large $k$,  {\em Proceedings of STOC 2015} 59--68.
\bibitem{DFFV} M. Dyer, A. Flaxman, A.M. Frieze and E. Vigoda, Randomly coloring sparse random graphs with fewer colors than the maximum degree, {\em Random Structures and Algorithms} 29 (2006) 450--465.
\bibitem{GM} G. Grimmett and C. McDiarmid, On colouring random graphs,
{\em Mathematical Proceedings of the Cambridge Philosophical Society} 77 (1975) 313--324.
\bibitem{JLR} S. Janson, T. {\L}uczak and A. Ruci\'nski, Random Graphs, Wiley 2000.
\bibitem{KMRSZ} F. Krzak\c{a}la, A. Montanari, F. Ricci-Tersenghi, G. Semerijian and  L. Zdeborov\'a, Gibbs states and the set of solutins of random constraint satisfaction problems, {\em Proceedings of the National Academy of Sciences} 104 (2007) 10318--10323.
\bibitem{M} M. Molloy,  The freezing threshold for $k$-colourings of a random graph, {\em Proceedings of STOC 2012}.
\bibitem{SU} E. Shamir and E. Upfal, Sequential and Distributed Graph Coloring Algorithms with Performance Analysis in Random Graph Spaces, {\em Journal of Algorithms} 5 (1984) 488--501.
\bibitem{ZK} L. Zdeborov\'a and F. Krzak\c{a}la, Phase Transitions in the Coloring of Random
Graphs, {\em Physics Review E} 76 (2007).
\end{thebibliography}
\end{document}

