Constraining the clustering transition for colorings of sparse random graphs

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 $\{\sigma ,\tau \}$ where $\sigma ,\tau$ are mappings $[n]\to [q]$ iff $h(\sigma ,\tau )=1$. Here $h(\sigma ,\tau )$ is the Hamming distance $|\{v\in [n]:\sigma (v)\ne \tau (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\ge \frac{cd}{\log d}$ for a constant $c>3/2$.