𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Mixing properties of the Swendsen–Wang process on classes of graphs

✍ Scribed by Colin Cooper; Alan M. Frieze

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
194 KB
Volume
15
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the mixing properties of the widely used Swendsen-Wang process for the Markov chain Monte Carlo estimation of the partition function of the ferromagnetic Q-state Potts model, for certain classes of graphs.

In the paper "The Swendsen-Wang Process Does Not Always Mix Rapidly," V. Gore and M. Jerrum obtained results for the mixing properties of the Swendsen-Wang process on the complete graph K n . Our main results for graphs with n vertices are the following:

• For graphs with small maximum degree, the mixing time is polynomial in n for small enough values of the coupling constant β. • For trees, the mixing time is O n for any β.

• For cycles, the mixing time is O n log n for any β.

• For random graphs G n p , p = n -1/3 , there are values of the coupling constant β for which whp the Swendsen-Wang process does not mix rapidly.

📜 SIMILAR VOLUMES

On the structure of extremal graphs of h
On the structure of extremal graphs of high girth
✍ Lazebnik, Felix; Wang, Ping 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB 👁 2 views

Let n ≥ 3 be a positive integer, and let G be a simple graph of order v containing no cycles of length smaller than n + 1 and having the greatest possible number of edges (an extremal graph). Does G contain an n + 1-cycle? In this paper we establish some properties of extremal graphs and present sev

On the generalization of thermodynamic p
On the generalization of thermodynamic properties for selection of bioseparation processes
✍ L A M van der Wielen; E S J Rudolph 📂 Article 📅 1999 🏛 Wiley (John Wiley & Sons) 🌐 English ⚖ 185 KB 👁 2 views

Rational selection of multiphase systems as required in bioseparation equipment and sequences in bioseparation processes beneüts tremendously from the availability of accurate and reliable thermodynamic data and predictive models. In this paper, we comment on a general methodology to correlate limit

On the vertex face total chromatic numbe
On the vertex face total chromatic number of planar graphs
✍ Weifan, Wang; Jiazhuang, Liu 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 471 KB 👁 2 views

Let G be a planar graph. The vertex face total chromatic number ,y13(G) of G is the least number of colors assigned to V(G) U F(G) such that no adjacent or incident elements receive the same color. The main results of this paper are as follows: (1) We give the vertex face total chromatic number for