Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings

Abstract

In this workwegive 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 ∈ C iff its geometric dual graph is a planar 3-tree. As a consequence, we show that every graph G ∈ C has at least 3·ϕ(|V(G)|+8)/30 ≥ 3·2(|V(G)|+8)/44 distinct perfect matchings, where ϕ is the golden ratio. Our bound improves (slightly) upon the 3·2(|V(G)|+12)/60 bound obtained by Cygan, Pilipczuk, and Škrekovski (2013) for the number of distinct perfect matchings also for graphs G ∈ 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.