Constraining the clustering transition for colorings of sparse random graphs

2017/05/22 by Anastos, Michael, Frieze, Alan, Pegden, Wesley
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1705.07944

Abstract

Let Ω_q denote the set of proper q-colorings of the random graph G_n,m, m=dn/2 and let H_q be the graph with vertex set Ω_q and an edge \σ,τ\ where σ,τ are mappings [n]→[q] iff h(σ,τ)=1. Here h(σ,τ) is the Hamming distance |\v∈ [n]:σ(v)≠τ(v)\|. We show that w.h.p. H_q contains a single giant component containing almost all colorings in Ω_q if d is sufficiently large and q≥ (cd)/(log d) for a constant c>3/2.

Related

• On the connectivity threshold for colorings of random graphs and hypergraphs
• Local convergence of random graph colorings
• The Clustering Coefficient of a Scale-Free Random Graph
• Chromatic thresholds in dense random graphs
• A critical point for random graphs with a given degree sequence