Path coupling using stopping times and counting independent sets and colorings in hypergraphs

DOI10.1002/rsa.20204zbMath1181.05061arXivmath/0501081OpenAlexW4236981399WikidataQ56323841 ScholiaQ56323841MaRDI QIDQ3503609

Magnus Bordewich, Martin Dyer, Marek Karpinski

Publication date: 5 June 2008

Published in: Random Structures and Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Markov chain Monte Carlohypergraph coloringpath couplinghypergraph independent set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete-time Markov processes on general state spaces (60J05) Hypergraphs (05C65) Enumeration in graph theory (05C30) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)

Related Items

The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs, On Sampling Simple Paths in Planar Graphs According to Their Lengths, On vertex independence number of uniform hypergraphs, Inapproximability of counting independent sets in linear hypergraphs, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, Approximation via Correlation Decay When Strong Spatial Mixing Fails, Counting hypergraph matchings up to uniqueness threshold, Sampling Eulerian orientations of triangular lattice graphs, Counting Hypergraph Colorings in the Local Lemma Regime, Approximate Counting via Correlation Decay in Spin Systems

Uses Software

• OEIS

Cites Work

• A new multilayered PCP and the hardness of hypergraph vertex cover
• Colouring graphs when the number of colours is nearly the maximum degree
• Automata, Languages and Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item