Improved bounds for sampling colorings

DOI10.1063/1.533196zbMath0978.60083OpenAlexW1976445742MaRDI QIDQ2737884

Publication date: 30 August 2001

Published in: Journal of Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1063/1.533196

zbMATH Keywords

Glauber dynamics rapidly mixing graph with maximum degree proper $k$-colorings

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coloring of graphs and hypergraphs (05C15)

Related Items

Randomly coloring simple hypergraphs with fewer colors, On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs, Paths between colourings of sparse graphs, Perfect sampling using bounding chains., Classifying coloring graphs, Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs, Algorithms to approximately count and sample conforming colorings of graphs, Sampling colourings of the triangular lattice, Unnamed Item, APPLICATION OF FINITE FIELD-DEPENDENT BRS TRANSFORMATIONS TO PROBLEMS OF THE COULOMB GAUGE, Random Instances of Problems in NP – Algorithms and Statistical Physics, Rigidity of 3-colorings of the discrete torus, Coupling with the stationary distribution and improved sampling for colorings and independent sets, An FPTAS for the hardcore model on random regular bipartite graphs, Phase transition for the mixing time of the Glauber dynamics for coloring regular trees, Forbidden subgraphs of coloring graphs, Kempe equivalence of 4‐critical planar graphs, Perfect sampling from spatial mixing, Rates of convergence for Gibbs sampling in the analysis of almost exchangeable data, What can be sampled locally?, Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials, On Vizing's edge colouring question, Block symmetries in graph coloring reconfiguration systems, Speeding up random walk mixing by starting from a uniform vertex, Correlation decay and deterministic FPTAS for counting colorings of a graph, On a recolouring version of Hadwiger's conjecture, Reconfiguration graphs of zero forcing sets, Exact thresholds for Ising-Gibbs samplers on general graphs, Randomly coloring simple hypergraphs, Rigidity of proper colorings of $\mathbb{Z}^d $, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Online Edge Coloring via Tree Recurrences and Correlation Decay, Some Problems on Approximate Counting in Graphs and Matroids, Unnamed Item, Kempe equivalence of colourings of cubic graphs, On a conjecture of Mohar concerning Kempe equivalence of regular graphs, Unnamed Item, Counting Constraint Satisfaction Problems., A general lower bound for mixing of single-site dynamics on graphs, Path coupling without contraction, Cut-colorings in coloring graphs, Counting Independent Sets and Colorings on Random Regular Bipartite Graphs, Connectedness of the graph of vertex-colourings, Counting proper colourings in 4-regular graphs via the Potts model, ABSENCE OF NONLOCAL COUNTERTERMS IN THE GAUGE BOSON PROPAGATOR IN AXIAL-TYPE GAUGES, Efficiency test of pseudorandom number generators using random walks, Glauber dynamics on trees: Boundary conditions and mixing time, CONNECTING GREEN FUNCTIONS IN AN ARBITRARY PAIR OF GAUGES AND AN APPLICATION TO PLANAR GAUGES, On systematic scan for sampling H-colorings of the path, Randomly coloring random graphs, Unnamed Item, Frozen colourings of bounded degree graphs, Kempe equivalence of colourings of cubic graphs, Matrix norms and rapid mixing for spin systems, Diameter of colorings under Kempe changes, Rapid mixing for lattice colourings with fewer colours, The Glauber dynamics for edge‐colorings of trees, Weighted counting of solutions to sparse systems of equations, Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice, Counting Hypergraph Colorings in the Local Lemma Regime, Random walks on a finite graph with congestion points, Approximate Counting via Correlation Decay in Spin Systems, Deterministic counting of graph colourings using sequences of subgraphs, Frozen (Δ + 1)-colourings of bounded degree graphs, Local uniformity properties for glauber dynamics on graph colorings, Randomly coloring constant degree graphs, A Simple Algorithm for Sampling Colorings of $G(n,d/n)$ Up to The Gibbs Uniqueness Threshold, Dynamic Sampling from Graphical Models, On mixing of Markov chains: coupling, spectral independence, and entropy factorization, Strong spatial mixing of list coloring of graphs, Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs

Cites Work