Geodesic
Constraining the clustering transition for colorings of sparse random graphs
Michael Anastos1 ; Alan Frieze1 ; Wesley Pegden1
1Carnegie Mellon University
The electronic journal of combinatorics, Tome 25 (2018) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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]\to[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$.
DOI : 10.37236/7040
Classification : 05C80
Mots-clés : random graphs, coloring, clustering transition

Michael Anastos  1   ; Alan Frieze  1   ; Wesley Pegden  1

1 Carnegie Mellon University 
@article{10_37236_7040,
     author = {Michael Anastos and Alan Frieze and Wesley Pegden},
     title = {Constraining the clustering transition for colorings of sparse random graphs},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {1},
     doi = {10.37236/7040},
     zbl = {1391.05225},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7040/}
}
TY  - JOUR
AU  - Michael Anastos
AU  - Alan Frieze
AU  - Wesley Pegden
TI  - Constraining the clustering transition for colorings of sparse random graphs
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7040/
DO  - 10.37236/7040
ID  - 10_37236_7040
ER  - 
%0 Journal Article
%A Michael Anastos
%A Alan Frieze
%A Wesley Pegden
%T Constraining the clustering transition for colorings of sparse random graphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7040/
%R 10.37236/7040
%F 10_37236_7040
Michael Anastos; Alan Frieze; Wesley Pegden. Constraining the clustering transition for colorings of sparse random graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 1. doi: 10.37236/7040

Cité par Sources :