## Abstract

We study the mixing time of the Swendsen-Wang dynamics for the ferromagnetic Ising and Potts models on the integer lattice Zd. This dynamics is a widely used Markov chain that has largely resisted sharp analysis because it is non-local, i.e., it changes the entire configuration in one step. We prove that, whenever strong spatial mixing (SSM) holds, the mixing time on any n-vertex cube in Zd is O(logn), and we prove this is tight by establishing a matching lower bound. The previous best known bound was O(n). SSM is a standard condition corresponding to exponential decay of correlations with distance between spins on the lattice and is known to hold in d=2 dimensions throughout the high-temperature (single phase) region. Our result follows from a modified log-Sobolev inequality, which expresses the fact that the dynamics contracts relative entropy at a constant rate at each step. The proof of this fact utilizes a new factorization of the entropy in the joint probability space over spins and edges that underlies the Swendsen-Wang dynamics, which extends to general bipartite graphs of bounded degree. This factorization leads to several additional results, including mixing time bounds for a number of natural local and non-local Markov chains on the joint space, as well as for the standard random-cluster dynamics.

Original language | English (US) |
---|---|

Title of host publication | STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Samir Khuller, Virginia Vassilevska Williams |

Publisher | Association for Computing Machinery |

Pages | 1551-1564 |

Number of pages | 14 |

ISBN (Electronic) | 9781450380539 |

DOIs | |

State | Published - Jun 15 2021 |

Event | 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy Duration: Jun 21 2021 → Jun 25 2021 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 |
---|---|

Country/Territory | Italy |

City | Virtual, Online |

Period | 6/21/21 → 6/25/21 |

## All Science Journal Classification (ASJC) codes

- Software

## Fingerprint

Dive into the research topics of 'Entropy Decay in the Swendsen Wang Dynamics on Z^{d}'. Together they form a unique fingerprint.