On the independence complex of square grids
From MaRDI portal
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 Fendleyet 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,-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.
Recommendations
- Special cycles in independence complexes and superfrustration in some lattices
- Hard squares with negative activity and rhombus tilings of the plane
- Hard squares with negative activity on cylinders with odd circumference
- Maximal independent sets on a grid graph
- Matching and independence complexes related to small grids
Cites work
- A user's guide to discrete Morse theory
- Complexes of directed trees
- Hard squares with negative activity
- Hard squares with negative activity and rhombus tilings of the plane
- scientific article; zbMATH DE number 4102053 (Why is no real title available?)
- scientific article; zbMATH DE number 1033382 (Why is no real title available?)
- scientific article; zbMATH DE number 758277 (Why is no real title available?)
- Independence complexes of claw-free graphs
- Morse theory for cell complexes
- Simplicial Complexes of Graphs and Hypergraphs with a Bounded Covering Number
Cited in
(32)- Upper bounds on the Witten index for supersymmetric lattice models by discrete Morse theory
- Complexes of directed trees and independence complexes
- The cyclomatic number of a graph and its independence polynomial at - 1
- Matching complexes of trees and applications of the matching tree algorithm
- Distance \(r\)-domination number and \(r\)-independence complexes of graphs
- Proof of the Kalai-Meshulam conjecture
- Matching and independence complexes related to small grids
- Every grid has an independent \([1, 2]\)-set
- Hard squares with negative activity and rhombus tilings of the plane
- Matching trees for simplicial complexes and homotopy type of devoid complexes of graphs
- A note on the values of independence polynomials at \(-1\)
- Special cycles in independence complexes and superfrustration in some lattices
- Star clusters in independence complexes of graphs
- On the homotopy types of the independence complexes of grid graphs with cylindrical identification
- Coxeter cochain complexes
- Higher independence complexes of graphs and their homotopy types
- On the homology of independence complexes
- The Rank-Width of the Square Grid
- A simple proof of an inequality connecting the alternating number of independent sets and the decycling number
- Independence complexes of \((n \times 4)\) and \((n \times 5)\)-grid graphs
- Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
- Sectionable tournaments: their topology and coloring
- Entanglement entropy in the ground state of supersymmetric fermion lattice models
- Hard squares for \(z = -1\)
- Dominance complexes, neighborhood complexes and combinatorial Alexander duals
- Vietoris-Rips complexes of torus grids
- The total Betti number of the independence complex of ternary graphs
- On the homotopy type of the polyhedral join over the independence complex of a forest
- Exploring homological properties of independence complexes of Kneser graphs
- A note on the alternating number of independent sets in a graph
- Cores of simplicial complexes
- Certain homology cycles of the independence complex of grids
This page was built for publication: On the independence complex of square grids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q930427)
