% -*- mode: latex; TeX-PDF-mode: t; -*- \documentclass[12pt]{article} \usepackage{e-jc} %% Added by CSG \specs{AA}{BB}{CC} %\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{hyperref} %\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}} \begin{document} \title{Constraining the clustering transition for\\ colorings of sparse random graphs} \author{Michael Anastos, Alan Frieze\thanks{Research supported in part by NSF grant DMS1362785}~~and Wesley Pegden\thanks{Research supported in part by NSF grant DMS1363136}\\Department of Mathematical Sciences\\Carnegie Mellon University\\Pittsburgh PA 15213} %% Added by CSG \date{\dateline{May 23, 2017}{Mar 7, 2018}{CC}\\ \small Mathematics Subject Classifications: 05C80} \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 $q3/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. {\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 $sInitialise: $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\>{\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. $\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 {\bf 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$, arxiv.org/pdf/1411.0650.pdf. \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}