Upper-bounding the \(k\)-colorability threshold by counting covers
type: Item
instance of: scholarly article
title: Upper-bounding the \(k\)-colorability threshold by counting covers
zbMATH Open document ID: 1298.05285
author: Amin Coja-Oghlan
published in: The Electronic Journal of Combinatorics
publication date: 2014-08-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/1305.0177
full work available at URL: v20i3p32
review text: 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\).
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q87
zbMATH DE Number: 6330304
zbMATH Keywords: random graphs
zbMATH Keywords: graph coloring
zbMATH Keywords: phase transitions
MaRDI profile type: Publication
arXiv ID: 1305.0177
cites work: Q4705349
cites work: Almost all graphs with 2. 522\(n\) edges are not 3-colorable
cites work: Almost all graphs with average degree 4 are 3-colorable
cites work: The two possible values of the chromatic number of a random graph
cites work: On the solution-space geometry of random constraint satisfaction problems
cites work: Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
cites work: The chromatic number of random graphs
cites work: Q4012216
cites work: On the chromatic number of random graphs
cites work: Tight Bounds on the Threshold for Permuted k-Colorability
cites work: The 3-XORSAT threshold.
cites work: An improved upper bound on the non-3-colourability threshold
cites work: Q3059475
cites work: Q3286850
cites work: Q4483917
cites work: Replica bounds for optimization problems and diluted spin systems
cites work: On colouring random graphs
cites work: Broken replica symmetry bounds in the mean field spin glass model
cites work: Q4519896
cites work: A note on the non-colorability threshold of a random graph
cites work: Poisson Cloning Model for Random Graphs
cites work: Gibbs states and the set of solutions of random constraint satisfaction problems
cites work: On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
cites work: Expose-and-merge exploration and the chromatic number of a random graph
cites work: Information, Physics, and Computation
cites work: The freezing threshold for k-colourings of a random graph
cites work: Coloring random graphs
cites work: Bounds for diluted mean-fields spin glass models
description: scientific article