Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings

Autor(es)

Jimenez, Andrea ^[1] ; Kiwi, Marcos ^{[2, 3]}

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508 Sao Paulo - Brazil

^[2] Univ Chile, Dept Ing Matemat, Santiago - Chile

^[3] Univ Chile, Ctr Modelamiento Matemat CNRS UMI 2807, Santiago - Chile

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 172, p. 45-61, JUL 31 2014.
• Citações Web of Science: 1

Resumo

In this work we give a lower bound for the groundstate degeneracy of the antiferromagnetic Ising model in the class of stack triangulations, also known as planar 3-trees. The geometric dual graphs of stack triangulations form a class, say C, of cubic bridgeless planar graphs, i.e. G is an element of C iff its geometric dual graph is a planar 3-tree. As a consequence, we show that every graph G is an element of C has at least 3.phi((vertical bar V(G)vertical bar+8)/30) >= 3.2((vertical bar V(G)vertical bar+8)/44) distinct perfect matchings, where phi is the golden ratio. Our bound improves (slightly) upon the 3.2((vertical bar V(G)vertical bar+12)/60) bound obtained by Cygan, Pilipczuk, and Skrekovski (2013) for the number of distinct perfect matchings also for graphs G is an element of C with at least 8 nodes. Our work builds on an alternative perspective relating the number of perfect matchings of cubic bridgeless planar graphs and the number of so called groundstates of the widely studied Ising model from statistical physics. With hindsight, key steps of our work can be rephrased in terms of standard graph theoretic concepts, without resorting to terminology from statistical physics. Throughout, we draw parallels between the terminology we rely on and some of the concepts introduced/developed independently elsewhere. (C) 2014 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 11/19978-5 - Imersão de Grafos em Superfícies e o Modelo de Ising
• Beneficiário: Andrea Patricia Jiménez Ramírez
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado