DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.23

Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences

Authors: Rupam Acharyya and Daniel Stefankovic

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

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).

Cite as

Rupam Acharyya and Daniel Stefankovic. Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{acharyya_et_al:LIPIcs.APPROX-RANDOM.2017.23,
  author =	{Acharyya, Rupam and Stefankovic, Daniel},
  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 =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.23},
  URN =		{urn:nbn:de:0030-drops-75724},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.23},
  annote =	{Keywords: Spin systems, Glauber dynamics, Ising model, graphons}
}

Search Results

Documents authored by Acharyya, Rupam

Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences

Abstract

Cite as

Thanks for your feedback!

Could not send message