Planting Colourings Silently

DOI10.1017/S0963548316000390zbMath1371.05068arXiv1411.0610MaRDI QIDQ5366948

Amin Coja-Oghlan, Charilaos Efthymiou, Victor Bapst

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

planted modelcondensation phase transition

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Related Items

Phase transitions in discrete structures, Information-theoretic thresholds from the cavity method, On the number of solutions in random hypergraph 2-colouring, On the connectivity of proper colorings of random graphs and hypergraphs, Charting the replica symmetric phase, Constraining the clustering transition for colorings of sparse random graphs, Unnamed Item, On the Number of Solutions in Random Graphk-Colouring, Rigid Colorings of Hypergraphs and Contiguity, The replica symmetric phase of random constraint satisfaction problems, Deterministic counting of graph colourings using sequences of subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Coloring random graphs
• Upper-bounding the \(k\)-colorability threshold by counting covers
• On the chromatic number of random regular graphs
• On the chromatic number of random \(d\)-regular graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• Expose-and-merge exploration and the chromatic number of a random graph
• A note on the sharp concentration of the chromatic number of random graphs
• The concentration of the chromatic number of random graphs
• Coloring Random Graphs
• Switching Colouring of G(n,d/n) for Sampling up to Gibbs Uniqueness Threshold
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Information, Physics, and Computation
• On colouring random graphs
• Almost all regular graphs are hamiltonian
• Paths in graphs
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• The Decimation Process in Random $k$-SAT
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Gibbs states and the set of solutions of random constraint satisfaction problems
• The freezing threshold for k-colourings of a random graph
• Going after the k-SAT threshold
• Frozen variables in random boolean constraint satisfaction problems
• The chromatic number of random graphs
• The chromatic number of random graphs
• The two possible values of the chromatic number of a random graph
• The condensation phase transition in random graph coloring