On the connectivity of proper colorings of random graphs and hypergraphs. Issue 4 (8th February 2020)

• Record Type: Journal Article
• Authors: Anastos, Michael; Frieze, Alan
• Is Part Of: Random structures & algorithms. Volume 56:Issue 4(2020)
• Page Start: 988
• Page End: 997
• Publication Date: 2020-02-08
• Subjects: random hypergraph coloring -- connectivity of colorings; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20912
• Languages: English
• ISSNs: 1042-9832

Abstract

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.