Geodesic
On the independence complex of square grids
Journal of Algebraic Combinatorics, Tome 27 (2008) no. 4, pp. 423-450.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: The enumeration of independent sets of regular graphs is of interest in statistical mechanics, as it corresponds to the solution of hard-particle models. In 2004, it was conjectured by Fendley et al., that for some rectangular grids, with toric boundary conditions, the $alternating$ number of independent sets is extremely simple. More precisely, under a coprimality condition on the sides of the rectangle, the number of independent sets of even and odd cardinality always differ by 1. In physics terms, this means looking at the hard-particle model on these grids at activity - 1. This conjecture was recently proved by Jonsson. Here we produce other families of grid graphs, with open or cylindric boundary conditions, for which similar properties hold without any size restriction: the number of independent sets of even and odd cardinality always differ by 0, $\pm 1$, or, in the cylindric case, by some power of 2.
Keywords: keywords hard particles, independent sets, independence complex, discrete Morse theory, transfer matrices 
@article{JAC_2008__27_4_a3,
     author = {Bousquet-M\'elou, Mireille and Linusson, Svante and Nevo, Eran},
     title = {On the independence complex of square grids},
     journal = {Journal of Algebraic Combinatorics},
     pages = {423--450},
     publisher = {mathdoc},
     volume = {27},
     number = {4},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2008__27_4_a3/}
}
TY  - JOUR
AU  - Bousquet-Mélou, Mireille
AU  - Linusson, Svante
AU  - Nevo, Eran
TI  - On the independence complex of square grids
JO  - Journal of Algebraic Combinatorics
PY  - 2008
SP  - 423
EP  - 450
VL  - 27
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2008__27_4_a3/
LA  - en
ID  - JAC_2008__27_4_a3
ER  - 
%0 Journal Article
%A Bousquet-Mélou, Mireille
%A Linusson, Svante
%A Nevo, Eran
%T On the independence complex of square grids
%J Journal of Algebraic Combinatorics
%D 2008
%P 423-450
%V 27
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2008__27_4_a3/
%G en
%F JAC_2008__27_4_a3
Bousquet-Mélou, Mireille; Linusson, Svante; Nevo, Eran. On the independence complex of square grids. Journal of Algebraic Combinatorics, Tome 27 (2008) no. 4, pp. 423-450. http://geodesic.mathdoc.fr/item/JAC_2008__27_4_a3/