On the connectivity threshold for colorings of random graphs and hypergraphs

2018/03/14 by Anastos, Michael, Frieze, Alan
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1803.05246

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 and an edge σ,τ\ where σ,τ are colorings iff h(σ,τ)=1. Here h(σ,τ) is the Hamming distance |\v∈ V(H):σ(v)≠τ(v)\|. We show that if H=H_n,m;k, k≥ 2, the random k-uniform hypergraph with V=[n] and m=dn/k then w.h.p. Γ_q is connected if d is sufficiently large and q\gtrsim (d/log d)^1/(k-1).

Related

• Threshold and hitting time for high-order connectivity in random hypergraphs
• Constraining the clustering transition for colorings of sparse random graphs
• A sharp threshold of propagation connectivity for mixed random hypergraphs
• Connectivity Threshold for random subgraphs of the Hamming graph
• On r-colorability of random hypergraphs