The number of independent sets in a grid graph

被引：126

作者：

Calkin, NJ ^{[1
]}

Wilf, HS

机构：

[1] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

[2] Univ Penn, Dept Math, Philadelphia, PA 19104 USA

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1998年 / 11卷 / 01期

关键词：

independent sets; grid graphs;

D O I：

10.1137/S089548019528993X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

If f(m; n) is the (vertex) independence number of the m x n grid graph, then we show that the double limit eta [GRAPHICS] lim(m,n-->infinity);n ! f(m; n) 1/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 prove that 1.503047782... is less-than-or-equal-to eta less-than-or-equal to 1.5035148.... Numerical computations suggest that the true value of eta (the "hard square constant") is around 1.5030480824753323....

引用

页码：54 / 60

页数：7