Satisfying states of triangulations of a convex \(n\)-gon (Q2380473)

Motivated by a conjecture of Lovasz and Plummer which states that the number of perfect matchings of a 2-connected cubic graph is exponential in the number of vertices, the authors examine the number of satisfying states of a convex \(n\)-gon's triangulation. Briefly, a \textit{state} of a triangulation \(T\) is an assignment \(\sigma: V(T) \rightarrow \{-1, 1\}\). The state is \textit{satisfying} if exactly one edge \((u, v)\) of each face of \(T\) satisfies \(\sigma(u) = \sigma(v)\). In the context of the Ising model, the satisfying states coincide with the groundstates. The authors first count the number of satisfying states of a triangulation \(T\) of an \(n\)-gon in the case when \(T\) has no \textit{interior faces} (that is, faces not sharing an edge with the boundary of the \(n\)-gon). The proof is constructive, using operations from which any such triangulation may be built up. These operations can also be nicely interpreted by using the planar dual of the triangulation. Using the transfer matrix method in a later section, the first main result of the paper states that the number of satisfying states of a triangulation of an \(n\)-gon with no interior faces is the (n+1)st Fibonacci number. Turning their attention to all triangulations of the \(n\)-gon, the authors provide an algorithm for constructing interior faces. Again using the transfer matrix method, they provide a lower bound for the number of satisfying states of such a triangulation. That is, if \(T\) is a triangulation of a convex \(n\)-gon, they prove that \(T\) has at least \(\phi^{2+n/2}\) satisfying states, where \(\phi\) is the golden ratio.