Upper-bounding the \(k\)-colorability threshold by counting covers (Q396853)

Summary: Let \(G(n,m)\) be a 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. 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\).