Details

Autor(en) / Beteiligte

• CALKIN, N. J
• WILF, H. S

Titel

The number of independent sets in a grid graph

Ist Teil von

• SIAM journal on discrete mathematics, 1998-02, Vol.11 (1), p.54-60

Ort / Verlag

Philadelphia, PA: Society for Industrial and Applied Mathematics

Erscheinungsjahr

1998

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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... .