Upper-bounding the \(k\)-colorability threshold by counting covers
The electronic journal of combinatorics, Tome 20 (2013) no. 3
Let $G(n,m)$ be the random graph on $n$ vertices with $m$ edges. Let $d=2m/n$ be its average degree. We prove that $G(n,m)$ fails to be $k$-colorable with high probability if $d>2k\ln k-\ln k-1+o_k(1)$. This matches a conjecture put forward on the basis of sophisticated but non-rigorous statistical physics ideas (Krzakala, Pagnani, Weigt: Phys. Rev. E 70 (2004)). The proof is based on applying the first moment method to the number of "covers", a physics-inspired concept. By comparison, a standard first moment over the number of $k$-colorings shows that $G(n,m)$ is not $k$-colorable with high probability if $d>2k\ln k-k$.
DOI :
10.37236/3337
Classification :
05C80, 05C15, 68Q87
Mots-clés : random graphs, graph coloring, phase transitions
Mots-clés : random graphs, graph coloring, phase transitions
Affiliations des auteurs :
Amin Coja-Oghlan 1
@article{10_37236_3337,
author = {Amin Coja-Oghlan},
title = {Upper-bounding the \(k\)-colorability threshold by counting covers},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {3},
doi = {10.37236/3337},
zbl = {1298.05285},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3337/}
}
Amin Coja-Oghlan. Upper-bounding the \(k\)-colorability threshold by counting covers. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/3337
Cité par Sources :