✦ LIBER ✦

On Markov Chains for Randomly H-Coloring a Graph

✍ Scribed by Colin Cooper; Martin Dyer; Alan Frieze

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 144 KB
Volume: 39
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1142

No coin nor oath required. For personal study only.

✦ Synopsis

Let H = W F be a graph without multiple edges, but with the possibility of having loops. Let G = V E be a simple graph. A homomorphism c is a map c V → W with the property that v w ∈ E implies that c v c w ∈ F. We will often refer to c v as the color of v and c as an H-coloring of G. We consider the problem of choosing a random H-coloring of G by Markov chain Monte Carlo. The probabilistic model we consider includes random proper colorings, random independent sets, and the Widom-Rowlinson and Beach models of statistical physics. We prove negative results for uniform sampling and a positive result for weighted sampling when H is a tree.

📜 SIMILAR VOLUMES

A more rapidly mixing Markov chain for g

A more rapidly mixing Markov chain for graph colorings

✍ Martin Dyer; Catherine Greenhill 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 351 KB 👁 2 views

We define a new Markov chain on proper k-colorings of graphs, and relate its convergence properties to the maximum degree ⌬ of the graph. The chain is shown to have bounds on convergence time appreciably better than those for the well-known JerrumrSalas᎐Sokal chain in most circumstances. For the cas

Very rapidly mixing Markov chains for 2Δ

Very rapidly mixing Markov chains for 2Δ-colorings and for independent sets in a graph with maximum degree 4

✍ Michael Molloy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A

On the First-Order Edgeworth Expansion f

On the First-Order Edgeworth Expansion for a Markov Chain

✍ S. Datta; W.P. Mccormick 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 474 KB

We consider the first-order Edgeworth expansion for summands related to a homogeneous Markov chain. Certain inaccuracies in some earlier results by Nagaev are corrected and the expansion is obtained under relaxed conditions. An application of our result to the distribution of the mle of a transition

On the edge-coloring problem for a class

On the edge-coloring problem for a class of 4-regular maps

✍ F. Jaeger; H. Shank 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB 👁 1 views

## Abstract A (plane) 4‐regular map __G__ is called __C__‐simple if it arises as a superposition of simple closed curves (tangencies are not allowed); in this case σ (__G__) is the smallest integer __k__ such that the curves of __G__ can be colored with __k__ colors in such a way that no two curves

Reconstruction of extended cortical sour

Reconstruction of extended cortical sources for EEG and MEG based on a Monte-Carlo-Markov-chain estimator

✍ Wilhelm Emil Kincses; Christoph Braun; Stefan Kaiser; Wolfgang Grodd; Hermann Ac 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 531 KB

## Abstract A new procedure to model extended cortical sources from EEG and MEG recordings based on a probabilistic approach is presented. The method (SPMECS) was implemented within the framework of maximum likelihood estimators. Neuronal activity generating EEG or MEG signals was characterized by

Erratum: On the edge-coloring problem fo

Erratum: On the edge-coloring problem for a class of 4-regular maps

✍ F. Jaeger; H. Shank 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 37 KB 👁 1 views

On p. 272 of the above article, paragraph # 3 is incomplete. It should read as the following: Hence to prove Proposition 4 it is enough to show that the edges of Q 4 can be colored with 4 colors in such a way that each square has one edge of each color. Such a coloring is displayed on the following