On the independence complex of square grids
Mireille Bousquet-Mélou1
, Svante Linusson2
and Eran Nevo3
1Université Bordeaux 1 CNRS, LaBRI 351 cours de la Libération 33405 Talence Cedex France
2KTH-Royal Institute of Technology Dept. of Mathematics 100 44 Stockholm Sweden
3Hebrew University Institute of Mathematics Jerusalem Israel
2KTH-Royal Institute of Technology Dept. of Mathematics 100 44 Stockholm Sweden
3Hebrew University Institute of Mathematics Jerusalem Israel
DOI: 10.1007/s10801-007-0096-x
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, \pm 1, or, in the cylindric case, by some power of 2.
Pages: 423–450
Keywords: keywords hard particles; independent sets; independence complex; discrete Morse theory; transfer matrices
Full Text: PDF
References
1. Baxter, R.J.: Hard hexagons: exact solution. J. Phys. A 13(3), L61-L70 (1980)
2. Engström, A.: Independence complexes of claw-free graphs. ArXiv:math.CO/0512420 (2005)
3. Fendley, P., Schoutens, K., van Eerten, H.: Hard squares with negative activity. J. Phys. A 38(2), 315-322 (2005), ArXiv:cond-mat/0408497
4. Forman, R.: Morse theory for cell complexes. Adv. Math. 134(1), 90-145 (1998) J Algebr Comb (2008) 27: 423-450
2. Engström, A.: Independence complexes of claw-free graphs. ArXiv:math.CO/0512420 (2005)
3. Fendley, P., Schoutens, K., van Eerten, H.: Hard squares with negative activity. J. Phys. A 38(2), 315-322 (2005), ArXiv:cond-mat/0408497
4. Forman, R.: Morse theory for cell complexes. Adv. Math. 134(1), 90-145 (1998) J Algebr Comb (2008) 27: 423-450
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition