License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.23
URN: urn:nbn:de:0030-drops-75724
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7572/
Go to the corresponding LIPIcs Volume Portal

Acharyya, Rupam ; Stefankovic, Daniel

Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences

pdf-format:
LIPIcs-APPROX-RANDOM-2017-23.pdf (0.6 MB)

Abstract

We study the Glauber dynamics for Ising model on (sequences of) dense graphs. We view the dense graphs through the lens of graphons. For the ferromagnetic Ising model with inverse temperature beta on a convergent sequence of graphs G_n with limit graphon W we show fast mixing of the Glauber dynamics if beta * lambda_1(W) < 1$ and slow (torpid) mixing if beta * lambda_1(W) > 1 (where lambda_1(W)is the largest eigenvalue of the graphon). We also show that in the case beta * lambda_1(W) = 1 there is insufficient information to determine the mixing time (it can be either fast or slow).

BibTeX - Entry

@InProceedings{acharyya_et_al:LIPIcs:2017:7572,
  author =	{Rupam Acharyya and Daniel Stefankovic},
  title =	{{Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7572},
  URN =		{urn:nbn:de:0030-drops-75724},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.23},
  annote =	{Keywords: Spin systems, Glauber dynamics, Ising model, graphons}
}

Keywords: Spin systems, Glauber dynamics, Ising model, graphons
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Issue Date: 2017
Date of publication: 11.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI