Sampling in Potts model on sparse random graphs

DOI10.4230/LIPICS.APPROX-RANDOM.2016.47MaRDI QIDQ4636481zbMATH OpenOpenAlexFDO

Authors Yitong Yin, Chihao Zhang

Publication date 19 April 2018

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/6670/pdf/LIPIcs-APPROX-RANDOM-2016-47.pdf/

zbMATH Keywords

samplingrandom graphapproximation algorithmPotts model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Random sampling of colourings of sparse random graphs with a constant number of colours
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Sampling random colorings of sparse random graphs
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• scientific article; zbMATH DE number 5279368

Cited in

(8)

• Deterministic counting of graph colourings using sequences of subgraphs
• A Simple Algorithm for Sampling Colorings of G(n,d/n) Up to The Gibbs Uniqueness Threshold
• Efficient Simulation of Sparse Graphs of Point Processes
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Counting solutions to random CNF formulas
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Counting solutions to random CNF formulas

This page was built for publication: Sampling in Potts model on sparse random graphs

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