The number of independent sets in a grid graph

If f(m,n) is the (vertex) independence number of the $m\times n$ grid graph, then we show that the double limit $\eta\eqdef\lim_{m,n\to\infty}f(m,n)^{1\over {mn}}$ exists, thereby refining earlier results of Weber [Rostock. Math. Kolloq., 34 (1988), pp. 28--36] and Engel [Fibonacci Quart.,, 28 (1990...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 1998-02, Vol.11 (1), p.54-60
Main Authors: CALKIN, N. J, WILF, H. S
Format: Article
Language:English
Subjects:
Applied mathematics
Classical combinatorial problems
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Mathematics
Sciences and techniques of general use
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:If f(m,n) is the (vertex) independence number of the $m\times n$ grid graph, then we show that the double limit $\eta\eqdef\lim_{m,n\to\infty}f(m,n)^{1\over {mn}}$ exists, thereby refining earlier results of Weber [Rostock. Math. Kolloq., 34 (1988), pp. 28--36] and Engel [Fibonacci Quart.,, 28 (1990), pp. 72--78]. We establish upper and lower bounds for $\eta$ and {\it prove} that $1.503047782... \le \eta \le 1.5035148\ldots $. Numerical computations suggest that the true value of $\eta$ (the "hard square constant") is around 1.5030480824753323... .
ISSN:0895-4801
1095-7146
DOI:10.1137/S089548019528993X