The Number of Independent Sets in a Grid Graph
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.
- Random maximal independent sets and the unfriendly theater seating arrangement problem
- Sequential cavity method for computing free energy and surface pressure
- Planar lattice gases with nearest-neighbor exclusion
- Several constants arising in statistical mechanics
- Upper bounds on the growth rates of independent sets in two dimensions via corner transfer matrices
- The transfer matrices and the capacity of the 2-dimensional (1, )-runlength limited constraint
- Constructing edge-disjoint Steiner paths in lexicographic product networks
- On the number of maximal independent sets in complete \(q\)-ary trees
- New upper and lower bounds on the channel capacity of read/write isolated memory
- Merrifield-Simmons index and its entropy of the 4-8-8 lattice
- Enumeration of matchings in complete q-ary trees
- The number of independent sets in an irregular graph
- Excuse me! or the courteous theatregoers' problem
- Graphs, partitions and Fibonacci numbers
- Enumeration problems for classes of self-similar graphs
- Extremal polyomino chains on k-matchings and k-independent sets
- Every grid has an independent \([1, 2]\)-set
- Nonograms: combinatorial questions and algorithms
- Theory of computation of multidimensional entropy with an application to the monomer-dimer problem
- Monochromatic connectivity and graph products
- Path-connectivity of lexicographic product graphs
- Counting maximal distance-independent sets in grid graphs
- Maximal independent sets in grid graphs
- Tutte polynomials for benzenoid systems with one branched hexagon
- REPETITIONS, FULLNESS, AND UNIFORMITY IN TWO-DIMENSIONAL WORDS
- Reconstruction of binary matrices under adjacency constraints
- Capacity of higher-dimensional constrained systems
- scientific article; zbMATH DE number 4059411 (Why is no real title available?)
- On generating functions and limit theorems associated with maximal independent sets in grid graphs
- The spectrum and spanning trees of polyominos on the torus
- Enumerating independent vertex sets in grid graphs
- Independent sets in graphs
- A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems
- The \(k\)-independence number of graph products
- Constructing internally disjoint pendant Steiner trees in Cartesian product networks
- Rainbow vertex-connection and graph products
- Independence complexes of \((n \times 4)\) and \((n \times 5)\)-grid graphs
- Asymptotic behavior of a generalized independent sets model on the two-dimensional Sierpinski gasket
- Enumerating maximal dissociation sets in three classes of grid graphs
- The g-good-neighbor diagnosability of product networks under the PMC model
- Approximating the hard square entropy constant with probabilistic methods
- The channel capacity of read/write isolated memory
This page was built for publication: The Number of Independent Sets in a Grid Graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388978)
