文章基本信息

标题：On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
本地全文：下载
作者：Michael Anastos ; Alan Frieze
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：145
页码：1-10
DOI：10.4230/LIPIcs.APPROX-RANDOM.2019.36
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Random Graphs; Colorings; Ergodicity