Upper-bounding the k-colorability threshold by counting covers

作者：Coja Oghlan Amin^*

来源：Electronic Journal of Combinatorics, 2013, 20(3): P32.

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 w.h.p. if d %26gt; 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 %26quot;covers%26quot;, 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 w.h.p. if d %26gt; 2k ln k - ln k.

• 出版日期2013-8-30