×

Independence complexes of \((n \times 4)\) and \((n \times 5)\)-grid graphs. (English) Zbl 1516.55010

Let \(G=(V,E)\) be a finite simple graph, where \(V\) and \(E\) denote the vertex set of \(V\) and the set of the edges of \(G\), respectively. A subset \(\sigma\subset V\) is called independent if there are no \(v,w\in \sigma\) such that \(\{v,w\}\in E\). The independence complex of a graph \(G=(V,E)\) is a simplicial complex whose vertex set is \(V\) and whose simplices are independent sets in \(V\). We denote by \(I(G)\) the independence complex of \(G\). For each pair \((n,k)\) of positive integers, let \(\Gamma_{n,k}=(V,E)\) denote the \((n\times k)\)-grid graph given by \begin{align*} V&=V(\Gamma_{n,k})=\{(x,y)\in \mathbb{Z}^2:1\leq k\leq n,1\leq y\leq k\}, \\ E&=E(\Gamma_{n,k})=\{\{(x,y),(z,w)\}:(x,y),(z,w)\in V, \vert x-z\vert+\vert y-w\vert =1\}. \end{align*}
In this paper, the authors investigate the homotopy type of the independence complex \(I(G)\) for \(G=\Gamma_{n,k}\). In particular, they prove that the independence complex \(I(\Gamma_{n,k})\) is homotopy equivalent to a wedge of spheres for \(k=4\) or \(k=5\) by using the fold lemma and its extended version.

MSC:

55P10 Homotopy equivalences in algebraic topology
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

References:

[1] Adamaszek, M., Splittings of independence complexes and the powers of cycles, J. Comb. Theory, Ser. A, 119, 1031-1047 (2012) · Zbl 1239.05196
[2] Adamaszek, M., Hard squares on cylinders revisited
[3] Barmak, J. A., Star clusters in independence complexes of graphs, Adv. Math., 241, 33-57 (2013) · Zbl 1288.57004
[4] Bayer, M.; Goeckner, B.; Jelić Milutinović, M., Manifold matching complexes, Mathematika, 66, 973-1002 (2020) · Zbl 1525.05200
[5] Braun, B.; Hough, W. K., Matching and independence complexes related to small grids, Electron. J. Comb., 18, 1 (2011) · Zbl 1229.05093
[6] Bousquet-Mélou, M.; Linusson, S.; Nevo, E., On the independence complex of square grids, J. Algebraic Comb., 27, 423-450 (2008) · Zbl 1202.05095
[7] Ehrenborg, R.; Hetyei, G., The topology of independence complex, Eur. J. Comb., 27, 906-923 (2006) · Zbl 1090.05075
[8] Engström, A., Complexes of directed trees and independence complexes, Discrete Math., 309, 3299-3309 (2009) · Zbl 1226.05084
[9] Goyal, S.; Shukla, S.; Singh, A., Matching complexes of \(3 \times \mathbf{n} \)-grid graphs, Electron. J. Comb., 28, 4 (2021), # P4.16 · Zbl 1482.05356
[10] Iriye, K., On the homotopy types of the independence complexes of grid graphs with cylindrical identification, Kyoto J. Math., 52, 3, 479-501 (2012) · Zbl 1248.05046
[11] Jonsson, J., Hard squares with negative activity and rhombus tilings of the plane, Electron. J. Comb., 13, 1, Article #R67 pp. (2006) · Zbl 1096.05004
[12] Jonsson, J., Hard squares with negative activity on cylinders with odd circumference, Electron. J. Comb., 16, 2, #R5 (2009) · Zbl 1187.05052
[13] Jonsson, J., Certain homology cycles of the independence complex of grids, Discrete Comput. Geom., 43, 4, 927-950 (2010) · Zbl 1220.05065
[14] Kozlov, D. N., Complexes of directed trees, J. Comb. Theory, Ser. A, 88, 112-122 (1999) · Zbl 0934.05041
[15] Kozlov, D. N., Combinatorial Algebraic Topology, Algorithms and Computation in Mathematics, vol. 21 (2008), Springer: Springer Berlin · Zbl 1157.57300
[16] Matsushita, T., Matching complexes of small grids, Electron. J. Comb., 26, 3 (July 2019) · Zbl 1416.05214
[17] Matsushita, T.; Wakatsuki, S., Independence complexes of \((n \times 6)\)-grid graphs, Homol. Homotopy Appl. (2023), in press
[18] Okura, K., Simple homotopy types of independence complexes of graphs involving grid graphs
[19] Polterovich, L.; Rosen, D.; Samvelyan, K.; Zhang, J., Topological Persistence in Geometry and Analysis, University Lecture Series (2020), American Mathematical Society · Zbl 1464.55003
[20] Thapper, J., Independence complexes of cylinders constructed from square and hexagonal grid graphs
[21] Wachs, M. L., Topology of matching, chessboard, and general bounded degree graph complexes, Algebra Univers., 49, 4, 345-385 (2003) · Zbl 1092.05511
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.