2026-07-24T05:46:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11251 2024-03-06T10:47:48Z ddc:004 open_access

On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs Anastos, Michael Frieze, Alan Random Graphs Colorings Ergodicity 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 where two vertices 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. Gamma_q is connected if d is sufficiently large and q >~ (d/log d)^{1/(k-1)}. This is optimal to the first order in d. Furthermore, with a few more colors, we find that the diameter of Gamma_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 Omega_q is ergodic w.h.p. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Anastos and Alan Frieze 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.36 urn:nbn:de:0030-drops-112513 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.36 eng https://creativecommons.org/licenses/by/3.0/legalcode