On the connectivity threshold for colorings of random graphs and hypergraphs

Abstract

Let ${\Omega }_q={\Omega }_q(H)$ denote the set of proper $[q]$-colorings of the hypergraph $H$. Let ${\Gamma }_q$ be the graph with vertex set ${\Omega }_q$ and an edge ${σ,τ\}$ where $\sigma ,\tau$ are colorings iff $h(\sigma ,\tau )=1$. Here $h(\sigma ,\tau )$ is the Hamming distance $|\{v\in V(H):\sigma (v)\ne \tau (v)\}|$. We show that if $H=H_{n,m;k},k\ge 2$, the random $k$-uniform hypergraph with $V=[n]$ and $m=dn/k$ then w.h.p. ${\Gamma }_q$ is connected if $d$ is sufficiently large and $q\gtrsim (d/\log d{)}^{1/(k-1)}$.

Added a bound on the diameter