Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the independence complex of square grids
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).ORCID iD: 0000-0001-6339-2230
2008 (English)In: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192, Vol. 27, no 4, 423-450 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2008. Vol. 27, no 4, 423-450 p.
Keyword [en]
hard particles, independent sets, independence complex, discrete morse, theory, transfer matrices
Identifiers
URN: urn:nbn:se:kth:diva-17459DOI: 10.1007/s10801-007-0096-xISI: 000255092400002Scopus ID: 2-s2.0-42449110848OAI: oai:DiVA.org:kth-17459DiVA: diva2:335503
Note
QC 20100525Available from: 2010-08-05 Created: 2010-08-05 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Linusson, Svante

Search in DiVA

By author/editor
Linusson, Svante
By organisation
Mathematics (Div.)
In the same journal
Journal of Algebraic Combinatorics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 20 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf