On the independence complex of square grids
By Mireille Bousquet-M'elou, Svante Linusson, Eran Nevo. 2006
80 citations recorded by the source corpus.
Abstract 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, ±1, or, in the cylindric case, by some power of 2. We show that these results reflect a stronger property of the independence complexes of our graphs. We determine the homotopy type of these complexes using Forman’s discrete Morse theory. We find that these complexes are either contractible, or homotopic to a sphere, or, in the cylindric case, to a wedge of spheres. Finally, we use our enumerative results to determine the spectra of certain transfer matrices describing the hard-particle model on our graphs at activity −1. These results parallel certain conjectures of Fendley et al., proved by Jonsson in the toric case.
Subfields: Computational Theory and Mathematics, Condensed Matter Physics, Discrete Mathematics and Combinatorics
View Paper: https://www.semanticscholar.org/paper/782360a41342610576a562a5af1ddd68db098e07
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Condensed Matter Physics
In Discrete Mathematics and Combinatorics
Citations in the corpus
- Star clusters in independence complexes of graphs (2010, unknown): “rases. Independence complexes, graphs, simplicial complexes, homotopy types, homotopy invariants. † Supported by grant KAW 2005.0098 from the Knut and Alice Wallenberg Foundation. 1 2 J.A.BARMAK Nevo [10] for some square grids, Braun [11] for Stable Kneser graphs and Jonsson [22] for bipartite graph”
- Supersymmetry, lattice fermions, independence complexes and cohomology theory (2009, methodology): “For the lattices R(M, N), R̃(M, N) and Rc(M, N) the full cohomology problem has been solved using Morse theory [12].”