%AAnastos, Michael [Department of Mathematical Sciences Carnegie Mellon University Pittsburgh Pennsylvania]%AFrieze, Alan [Department of Mathematical Sciences Carnegie Mellon University Pittsburgh Pennsylvania]%BJournal Name: Random Structures & Algorithms; Journal Volume: 56; Journal Issue: 4; Related Information: CHORUS Timestamp: 2023-09-05 22:41:03
%D2020%IWiley Blackwell (John Wiley & Sons)
%JJournal Name: Random Structures & Algorithms; Journal Volume: 56; Journal Issue: 4; Related Information: CHORUS Timestamp: 2023-09-05 22:41:03
%K
%MOSTI ID: 10133767
%PMedium: X
%TOn the connectivity of proper colorings of random graphs and hypergraphs
%XLet Ω_{q}=Ω_{q}(H) denote the set of proper [q]‐colorings of the hypergraphH. 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 ifH=H_{n,m;k}, k ≥ 2, the randomk‐uniform hypergraph withV=[n] andm=dn/khyperedges then w.h.p. Γ_{q}is connected ifdis sufficiently large and. This is optimal up to the first order ind. Furthermore, with a few more colors, we find that the diameter of Γ_{q}isO(n) w.h.p., where the hidden constant depends ond. So, with this choice ofd,q, the natural Glauber dynamics Markov Chain on Ω_{q}is ergodic w.h.p.

%0Journal Article