Constraining the clustering transition for colorings of sparse random graphs (Q1753047)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Constraining the clustering transition for colorings of sparse random graphs |
scientific article |
Statements
Constraining the clustering transition for colorings of sparse random graphs (English)
0 references
25 May 2018
0 references
Summary: Let \(\Omega_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 \(\Omega_q\) and an edge \(\{\sigma,\tau\}\) where \(\sigma,\tau\) are mappings \([n]\rightarrow[q]\) iff \(h(\sigma,\tau)=1\). Here \(h(\sigma,\tau)\) is the Hamming distance \(|\{v\in [n]:\sigma(v)\neq\tau(v)\}|\). We show that w.h.p. \(H_q\) contains a single giant component containing almost all colorings in \(\Omega_q\) if \(d\) is sufficiently large and \(q\geq \frac{cd}{\log d}\) for a constant \(c>3/2\).
0 references
random graphs
0 references
coloring
0 references
clustering transition
0 references