A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold

DOI10.1137/140977643zbMath1355.68206arXiv1609.05934OpenAlexW2522859079MaRDI QIDQ5506696

Charilaos Efthymiou

Publication date: 13 December 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

efficient algorithmrandom coloringsparse random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (8)

Counting Solutions to Random CNF Formulas ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Uniqueness for the 3-state antiferromagnetic Potts model on the tree ⋮ Random-cluster dynamics on random regular graphs in tree uniqueness ⋮ Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs ⋮ Deterministic counting of graph colourings using sequences of subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Disagreement percolation in the study of Markov fields
• Uniqueness of uniform random colorings of regular trees
• Improved bounds for sampling colorings
• Randomly coloring constant degree graphs
• Switching Colouring of G(n,d/n) for Sampling up to Gibbs Uniqueness Threshold
• Counting independent sets up to the tree threshold
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Graphical Models, Exponential Families, and Variational Inference
• Sampling in Potts Model on Sparse Random Graphs
• Survey propagation: An algorithm for satisfiability
• MCMC sampling colourings and independent sets of G(n, d/n) near uniqueness threshold
• Strong Spatial Mixing with Fewer Colors for Lattice Graphs
• Gibbs rapidly samples colorings of \(G(n, d/n)\)

This page was built for publication: A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold