On the connectivity of proper colorings of random graphs and hypergraphs. Issue 4 (8th February 2020) - Anastos, Michael; Frieze, Alan
Abstract : Let Ω q =Ω q ( H ) denote the set of proper [ q ]‐colorings of the hypergraph H . Let Γ q be the graph with vertex set Ω q where two colorings σ, τ are adjacent iff the corresponding colorings differ in exactly one vertex. We show that if H = H n, m ; k, k ≥ 2, the random k ‐uniform hypergraph with V =[ n ] and m = dn / k hyperedges then w.h.p. Γ q is connected if d is sufficiently large and q ≳ ( d / log d ) 1 / ( k − 1 ) . This is optimal up to the first order in d . Furthermore, with a few more colors, we find that the diameter of Γ q is O ( n ) w.h.p., where the hidden constant depends on d . So, with this choice of d, q, the natural Glauber dynamics Markov Chain on Ω q is ergodic w.h.p.