Constraining the clustering transition for colorings of sparse random graphs (Q1753047)

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