Upper-bounding the k-colorability threshold by counting covers

MaRDI QIDQ396853zbMATH OpenFDO

Authors Amin Coja-Oghlan

Publication date 14 August 2014

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

Full work available at URL https://arxiv.org/abs/1305.0177, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p32

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

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)

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$.

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

Cites work

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

Cited in

(31)

• scientific article; zbMATH DE number 1919507 (Why is no real title available?)
• 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
• An improved upper bound on the non-3-colourability threshold
• Planting colourings silently
• Circular coloring of random graphs: statistical physics investigation
• The large deviations of the whitening process in random constraint satisfaction problems
• Inter-generational comparison of quantum annealers in solving hard scheduling problems
• Tight bounds on the threshold for permuted \(k\)-colorability
• The replica symmetric phase of random constraint satisfaction problems
• 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
• scientific article; zbMATH DE number 1553748 (Why is no real title available?)
• 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
• Lower bounds on the chromatic number of random graphs
• One-step replica symmetry breaking of random regular NAE-SAT. II

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)