Improved Bounds for the Number of Forests and Acyclic Orientations in the Square Lattice

Abstract

In a recent paper Merino and Welsh (1999) studied several counting problems on the square lattice $L_n$. There the authors gave the following bounds for the asymptotics of $f(n)$, the number of forests of $L_n$, and $\alpha(n)$, the number of acyclic orientations of $L_n$: $$3.209912 \le \lim_{n\to\infty} f(n)^{1/n^2} \le 3.84161$$ and $$22/7 \le \lim_{n\to\infty} \alpha(n)^{1/n^2} \le 3.70925.$$

In this paper we improve these bounds as follows: $$3.64497 \le \lim_{n\to\infty} f(n)^{1/n^2} \le 3.74101$$ and $$3.41358 \le \lim_{n\to\infty} \alpha(n)^{1/n^2} \le 3.55449.$$ We obtain this by developing a method for computing the Tutte polynomial of the square lattice and other related graphs based on transfer matrices.