Upper-bounding the k-colorability threshold by counting covers

zbMATH Open1298.05285arXiv1305.0177MaRDI QIDQ396853FDOQ396853

Authors: Amin Coja-Oghlan 

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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>2klnk-lnk-1+o_k(1)$. This matches a conjecture put forward on the basis of sophisticated but non-rigorous statistical physics ideas (Krzakala, Pagnani, Weigt 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 $gnm$ is not $k$-colorable with high probability if $d>2klnk-lnk$.

Full work available at URL: https://arxiv.org/abs/1305.0177

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• scientific article; zbMATH DE number 1380613
• On the 2-colorability of random hypergraphs
• scientific article; zbMATH DE number 1919507
• An improved upper bound on the non-3-colourability threshold
• Almost all graphs with 2. 522\(n\) edges are not 3-colorable

zbMATH Keywords

graph coloringphase transitionsrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The two possible values of the chromatic number of a random graph
• Bounds for diluted mean-fields spin glass models
• Replica bounds for optimization problems and diluted spin systems
• Broken replica symmetry bounds in the mean field spin glass model
• Title not available (Why is that?)
• An improved upper bound on the non-3-colourability threshold
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Expose-and-merge exploration and the chromatic number of a random graph
• Coloring random graphs
• Title not available (Why is that?)
• On colouring random graphs
• The chromatic number of random graphs
• Information, Physics, and Computation
• Title not available (Why is that?)
• The freezing threshold for \(k\)-colourings of a random graph
• Poisson Cloning Model for Random Graphs
• The chromatic number of random graphs
• On the solution-space geometry of random constraint satisfaction problems
• Almost all graphs with average degree 4 are 3-colorable
• Almost all graphs with 2. 522\(n\) edges are not 3-colorable
• The 3-XORSAT threshold.
• A note on the non-colorability threshold of a random graph
• Tight bounds on the threshold for permuted \(k\)-colorability
• Upper-bounding the \(k\)-colorability threshold by counting covers
• Title not available (Why is that?)
• On the chromatic number of random graphs
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas

Cited In (31)

• Upper-bounding the \(k\)-colorability threshold by counting covers
• On the structure of the set of panchromatic colorings of a random hypergraph
• Phase transitions in discrete structures
• On the chromatic numbers of random hypergraphs
• On the chromatic number of a random hypergraph
• On the strong chromatic number of a random 3-uniform hypergraph
• Estimating the \(r\)-colorability threshold for a random hypergraph
• Planting colourings silently
• Circular coloring of random graphs: statistical physics investigation
• The large deviations of the whitening process in random constraint satisfaction problems
• An improved upper bound on the non-3-colourability threshold
• Inter-generational comparison of quantum annealers in solving hard scheduling problems
• The replica symmetric phase of random constraint satisfaction problems
• Tight bounds on the threshold for permuted \(k\)-colorability
• On the chromatic number of random regular graphs
• On the strong chromatic number of random hypergraphs
• On two limit values of the chromatic number of a random hypergraph
• On the concentration of values of \(j\)-chromatic numbers of random hypergraphs
• On the concentration of the domination number of the random graph
• The condensation phase transition in random graph coloring
• Two values of the chromatic number of a sparse random graph
• An upper bound for van der Waerden-like numbers using \(k\) colors
• The asymptotic \(k\)-SAT threshold
• Title not available (Why is that?)
• A case study in programming a quantum annealer for hard operational planning problems
• On the number of solutions in random graph \(k\)-colouring
• Estimating the strong \(r\)-colorability threshold in random hypergraphs
• On the Potts antiferromagnet on random graphs
• One-step replica symmetry breaking of random regular NAE-SAT. II
• Lower bounds on the chromatic number of random graphs
• Title not available (Why is that?)

This page was built for publication: Upper-bounding the \(k\)-colorability threshold by counting covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396853)