REVIEW 3 minor 7 references
Simple homotopy types of independence complexes of graphs involving grid graphs
T0 review · 0 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Replacing a 2-by-2 or 3-by-2 square-grid patch inside a graph by a longer strip suspends the independence complex once or three times, and this gives exact simple homotopy types for several grid families.
desk verdict New simple homotopy type results for independence complexes of grid graphs, but the diagram-based proofs need a closer look at isolation conditions in the ambient graph. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the independence complex $I(G)$ together with three elementary moves derived from a collapse lemma: $\mathrm{Del}(v,u)$ deletes a vertex $v$ when $u$ is isolated in $G\setminus N[v]$, causing $I(G)$ to collapse onto $I(G-\{v\})$; $\mathrm{Del}(vw,u)$ deletes an edge $vw$ when $u$ is isolated in $G\setminus N[vw]$, causing an expansion from $I(G)$ to $I(G-vw)$; and $\mathrm{Add}(vw,u)$ adds the edge $vw$ when $u$ is isolated outside both closed neighborhoods, causing a collapse from $I(G)$ to $I(G\cup vw)$. Theorems 1.2 and 1.3 are proved by composing these moves in the explicit sequences displayed in Figures 7 through 10, transforming the larger graph $H$ into a disjoint union $G \sqcup e$ or $G \sqcup C_{1,8}$ without changing the simple homotopy type. The suspension then appears because $I(G\sqcup e)$ is simply homotopy equivalent to $\Sigma I(G)$, and $I(G\sqcup C_{1,8})$ to $\Sigma^3 I(G)$.
What would settle it
Take $G$ to be $P_{2,2}$ with one extra pendant vertex attached to one corner, form $H$ by replacing the $P_{2,2}$ with $P_{2,4}$, and compute the reduced Euler characteristics of $I(H)$ and $\Sigma I(G)$; if they differ, Theorem 1.2 fails. A direct check is to run the six operations in Figure 7 on this $G$ and see whether the first operation $\mathrm{Add}(14,3)$ has vertex 3 isolated in $G\setminus N[14]$.
Extended reading notes
Core claim
The central claim is that a local enlargement of a grid inside a graph produces a suspension of the independence complex in the simple homotopy sense. Simple homotopy equivalence means the two complexes can be transformed into each other by a finite sequence of elementary collapses and expansions. Precisely, let $G$ be a finite graph containing the square grid $P_{2,2}$ as a full subgraph, and let $H$ be obtained from $G$ by replacing that $P_{2,2}$ with the longer strip $P_{2,4}$ in the manner of Figure 1; then $I(H)$ is simple homotopy equivalent to $\Sigma I(G)$. Likewise, if $G$ contains $P_{3,2}$ as a full subgraph and the patch is replaced by $P_{3,6}$ as in Figure 2, then $I(H)$ is simple homotopy equivalent to $\Sigma^3 I(G)$. This generalizes the one-dimensional case where an edge of $G$ is replaced by a path of length four. The suspension statements are proved by writing down explicit sequences of elementary collapses and expansions, and the corollaries identify the simple homotopy types of the independence complexes of the cylindrical grid graphs $C_{1,n}$, $C_{2,n}$, $C_{3,n}$, the reflected cylindrical graphs $M_{2,n}$, $M_{3,n}$, and the hexagonal-cylinder graph $CH_{1,n}$ as spheres, joins, or wedges of spheres.
Load-bearing premise
The load-bearing premise is that the drawn move sequences in Figures 7 through 10 are valid for every ambient graph containing the relevant grid as a full subgraph: at each step the required isolated vertex must exist, and a single diagram error would break the corresponding theorem.
Editorial extensions
If this is right
- For the cylindrical family $C_{1,n}$, the independence complex $I(C_{1,3k+i})$ is either a single triangulated sphere, a wedge of two such spheres, or the one-point suspension of a sphere, depending on $i$ modulo 3.
- The larger cylinders are classified as wedges of spheres: for example $I(C_{2,4k})$ is the wedge of three $(2k-1)$-spheres and $I(C_{3,8k})$ is the wedge of five $(6k-1)$-spheres.
- The reflected cylindrical families $M_{2,n}$ and $M_{3,n}$ satisfy the same kind of suspension recurrences, so their independence complexes are also wedges of spheres with dimensions controlled by $n$ mod 4 or mod 8.
- The hexagonal-cylinder complex $I(CH_{1,n})$ is contractible for odd $n$ and is the wedge of two $(2k-1)$-spheres for $n=2k$.
- Because the proofs are by explicit simple homotopy moves, the classification holds in the simple homotopy category, not merely up to ordinary homotopy equivalence.
Reading between the lines
- The same move-sequence technology could be applied to replace other rectangular patches by longer strips, but the paper's Remark 3.2 shows the pattern stops at thickness 3: for a 4-by-$k$ grid the analogous identity would contradict a reduced Euler characteristic computation. Scanning larger $m$ with the same criterion would chart exactly which patch replacements are admissible.
- Because the Add/Del moves are local, several disjoint $P_{2,2}$ or $P_{3,2}$ patches in a single graph could be processed independently, so the suspension exponents would add; this gives a compositional recipe for computing simple homotopy types of larger grid complexes without drawing new diagrams.
- Simple homotopy equivalence preserves more structure than homology, so these results upgrade the earlier homotopy-type determinations and make the listed independence complexes identifiable up to simple homotopy, not just up to homotopy.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper refines Csorba's suspension theorem for independence complexes by upgrading homotopy equivalences to simple homotopy equivalences. Theorem 1.1 treats the replacement of an edge by a length-four path; Theorems 1.2 and 1.3 extend this to replacements of P_{2,2} by P_{2,4} and of P_{3,2} by P_{3,6}, giving one and three suspensions, respectively. The proofs are explicit sequences of the Add/Del operations introduced through Lemma 2.1, with diagrams. Corollaries 1.4–1.7 state simple homotopy types for independence complexes of cylindrical, Möbius, and hexagonal grid graphs. Remark 3.2 gives a non-extension result for the analogous m=4 replacement, supported by the reduced Euler characteristic computation in Appendix A.
Significance. The main contribution is a stronger, simple-homotopy form of known suspension results, with concrete consequences for several families of grid graphs. The proofs are elementary and explicit, and Appendix A is self-contained. I specifically examined the worry that Add/Del witnesses in Theorems 1.2 and 1.3 might have neighbors outside the displayed grid. Under the replacement rule described in Figures 1 and 2 and in Remark 3.2, the retained old vertices are the end columns of the new P_{m,k}, and all witnesses used in the operation lists are newly inserted vertices, which have no edges to the rest of G. The concern therefore does not land. The main limitation is that the proofs are diagram-dependent and the accented vertex notation is easy to misread.
minor comments (3)
- [Section 3, Proofs of Theorems 1.2 and 1.3] The authors should state explicitly that every witness in the Add/Del sequences is a newly inserted vertex of the replacement grid, so its neighborhood is contained in the displayed subgraph and cannot be affected by vertices outside the grid.
- [Section 3, notation] The vertex notation distinguishing rows (plain, bar, hat, tilde) is essential for verifying the operation lists; please define it immediately before Theorem 1.2 and ensure the figures use the same symbols consistently, since the distinction between old and new vertices is otherwise easy to miss.
- [Figures 7–10] A short sentence after each operation list noting that each listed step is a direct application of Lemma 2.1, with the required isolated vertex visible in the figure, would make the proofs easier to verify without requiring the reader to reverse-engineer the diagrams.
Circularity Check
No circularity: the main theorems are proved by explicit Add/Del collapse sequences and independent external lemmas.
full rationale
The paper's central claims, Theorems 1.1, 1.2, and 1.3, are established by explicit sequences of elementary collapses and expansions licensed by Lemma 2.1. No parameter is fitted to any output, and no theorem is assumed in order to prove itself. Theorem 1.3 invokes Corollary 1.4, but Corollary 1.4 is derived independently from Theorem 1.1 and explicit base cases, so this is not a circular dependency. The cited results of Csorba, Engström, Adamaszek, Kozlov, Thapper, and Iriye are external lemmas and prior theorems, and there are no load-bearing self-citations. The appendix computation of reduced Euler characteristics is independent of the main theorems and even used in Remark 3.2 to demonstrate that the pattern does not extend to the m=4 case, which further indicates that the main results are not vacuous or definitionally forced. Any concern about whether the diagrams fully certify the isolation conditions of Lemma 2.1 in arbitrary ambient graphs is a correctness gap, not a circularity: the proof strategy does not reduce to its inputs by construction. Therefore the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (2)
- domain assumption Adamaszek's cofiber sequence for edge removal (Lemma A.2)
- standard math Standard simple homotopy theory: elementary collapses and expansions preserve simple homotopy type
Cite this review
Pith. "Pith review of Simple homotopy types of independence complexes of graphs involving grid graphs." pith.science (2026). https://pith.science/paper/7E2TZAPA
@misc{pith2026190809356,
author = {Pith},
title = {Pith review of: Simple homotopy types of independence complexes of graphs involving grid graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/7E2TZAPA}},
note = {Machine review of arXiv:1908.09356}
}
abstract
We show that if a graph $G$ involves a certain square grid graph as a full subgraph, then a certain operation on it yields a simplicial suspension of the independence complex of $G$. This generalizes a result of Csorba. As a corollary, we determine the simple homotopy types of the independence complexes of some grid graphs.
Figures
Figures from the paper (21 more)
Reference graph
Works this paper leans on
-
[3]
P´ eter Csorba. Subdivision yields Alexander duality on independence complexes.The Electronic Journal of Combinatorics , 16(2):#R11, 2009
work page 2009
-
[1]
Hard squares on cylinders revisited
Micha l Adamaszek. Hard squares on cylinders revisited. arXiv e-prints, arXiv:1202.1655, Feb 2012
work page Pith review arXiv 2012
-
[2]
Splittings of independence complexes and the powers of cycles
Micha l Adamaszek. Splittings of independence complexes and the powers of cycles. Journal of Combinatorial Theory, Series A , 119:1031–1047, 2012
work page 2012
-
[4]
Complexes of directed trees and independence complexes.Discrete Math- ematics, 309:3299–3309, 2009
Alexander Engstr¨ om. Complexes of directed trees and independence complexes.Discrete Math- ematics, 309:3299–3309, 2009
work page 2009
-
[5]
On the homotopy types of the independence complexes of grid graphs with cylindrical identification
Kouyemon Iriye. On the homotopy types of the independence complexes of grid graphs with cylindrical identification. Kyoto Journal of Mathematics , 52(3):479–501, 2012
work page 2012
-
[6]
Dmitry N Kozlov. Complexes of directed trees. Journal of Combinatorial theory, Series A , 88:112–122, 1999
work page 1999
-
[7]
Independence Complexes of Cylinders Constructed from Square and Hexagonal Grid Graphs
Johan Thapper. Independence Complexes of Cylinders Constructed from Square and Hexag- onal Grid Graphs. arXiv e-prints, arXiv:0812.1165, Dec 2008. Sagano High School, 15, Tokiwadannoue-cho, Ukyo-ku, Kyoto, Japan E-mail address: okura.kengo.k35@kyoto-u.jp
work page Pith review arXiv 2008
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.