The Number of Independent Sets in a Grid Graph (Q4388978)

Let \(G_{m,n}\) be the \(m\times n\) grid graph, i.e. the graph whose vertices are the integer points \((i,j)\) (\(0\leq i\leq m\), \(0\leq j\leq n\)) in the plane and whose edge set consists of the pairs \(((i, j),(i',j'))\) of vertices for which \(| i-i'|+| j-j'|= 1\). Let \(f(m,n)\) be the number of independent sets in \(G_{m,n}\). The authors show that the double limit \[ \eta= \lim_{m,n\to\infty} f(m,n)^{1/mn} \] exists and prove that \(1.503047782\dots\leq\eta\leq 1.5035148\dots\)\ . The proof methods for the existence and the lower bound are the same as in \textit{K. Engel} [On the Fibonacci number of an \(m\times n\) lattice, Fibonacci Q. 28, No. 1, 72-78 (1990; Zbl 0686.05027)], where the slightly sharper lower bound \(1.50304808\dots\) was given (it is conjectured that this is the exact value). A nice interpretation of the trace of a power of a corresponding transfer matrix and the use of a second special transfer matrix leads to the new upper bound given above.