License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.36
URN: urn:nbn:de:0030-drops-147291
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14729/
Go to the corresponding LIPIcs Volume Portal

Galanis, Andreas ; Goldberg, Leslie Ann ; Stewart, James

Fast Mixing via Polymers for Random Graphs with Unbounded Degree

pdf-format:
LIPIcs-APPROX36.pdf (0.6 MB)

Abstract

The polymer model framework is a classical tool from statistical mechanics that has recently been used to obtain approximation algorithms for spin systems on classes of bounded-degree graphs; examples include the ferromagnetic Potts model on expanders and on the grid. One of the key ingredients in the analysis of polymer models is controlling the growth rate of the number of polymers, which has been typically achieved so far by invoking the bounded-degree assumption. Nevertheless, this assumption is often restrictive and obstructs the applicability of the method to more general graphs. For example, sparse random graphs typically have bounded average degree and good expansion properties, but they include vertices with unbounded degree, and therefore are excluded from the current polymer-model framework.
We develop a less restrictive framework for polymer models that relaxes the standard bounded-degree assumption, by reworking the relevant polymer models from the edge perspective. The edge perspective allows us to bound the growth rate of the number of polymers in terms of the total degree of polymers, which in turn can be related more easily to the expansion properties of the underlying graph. To apply our methods, we consider random graphs with unbounded degrees from a fixed degree sequence (with minimum degree at least 3) and obtain approximation algorithms for the ferromagnetic Potts model, which is a standard benchmark for polymer models. Our techniques also extend to more general spin systems.

BibTeX - Entry

@InProceedings{galanis_et_al:LIPIcs.APPROX/RANDOM.2021.36,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Stewart, James},
  title =	{{Fast Mixing via Polymers for Random Graphs with Unbounded Degree}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14729},
  URN =		{urn:nbn:de:0030-drops-147291},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.36},
  annote =	{Keywords: Markov chains, approximate counting, Potts model, expander graphs, random graphs}
}

Keywords: Markov chains, approximate counting, Potts model, expander graphs, random graphs
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue Date: 2021
Date of publication: 15.09.2021

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