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

approximation algorithmPotts modelrandom graphsampling

Mathematics Subject Classification ID

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

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

(9)

• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• Deterministic counting of graph colourings using sequences of subgraphs
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Counting solutions to random CNF formulas
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• 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
• Counting solutions to random CNF formulas
• Low-temperature sampling on sparse random graphs

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)