On Shellability of 3-Cut Complexes of Hexagonal Grid Graphs
Himanshu Chandrakar · 2025
Read On Shellability of 3-Cut Complexes of Hexagonal Grid Graphs by Himanshu Chandrakar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-21755.txt.
Introduction
Himanshu Chandrakar studies the three-cut complexes of hexagonal grid graphs, continuing a line of work on the topology of graph-based complexes. A k-cut complex is built from the subsets of vertices whose removal disconnects the graph in a controlled way. A complex is shellable when its largest pieces can be ordered so each new piece attaches cleanly to the earlier ones, which makes its shape easy to compute.
Chandrakar proves the three-cut complexes of all hexagonal grid graphs are shellable, by constructing an explicit shelling order from reverse lexicographic ordering. From that shelling he counts the spanning facets exactly, with a closed formula. The count implies the complex has the homotopy type of a wedge of that many spheres, all of one dimension that grows with the grid. General results already implied these facts abstractly; the contribution is the explicit construction.
Catalog record
| CREATOR | Himanshu Chandrakar |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-21755
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Shellability of 3-Cut Complexes of Hexagonal Grid Graphs Himanshu Chandrakar Abstract The k k -cut complex was recently introduced by Bayer et al. as a generalization of earlier work of Fröberg (1990) and Eagon and Reiner (1998), and was shown to be shellable for several classes of graphs. In this article, we prove that the 3 3 -cut complex of the hexagonal grid graph H 1 × m × n H_{1\times m\times n} is shellable for all m , n ≥ 1 m,n\geq 1 , by constructing an explicit shelling order using reverse lexicographic ordering. From this shelling, we determine the number of spanning facets, denoted by ψ m , n \psi_{m,n} , and deduce that the complex is homotopy equivalent to a wedge of ψ m , n \psi_{m,n} spheres of dimension ( 2 m + 2 n + 2 m n − 4 ) \left(2m+2n+2mn-4\right) , where ψ m , n = ( 2 m + 2 n + 2 m n − 1 2 ) − [ ( 6 m + 2 ) n + ( 2 m − 4 ) ] . \psi_{m,n}=\binom{2m+2n+2mn-1}{2}-\left[\left(6m+2\right)n+(2m-4)\right]. While these topological properties can be obtained from general results of Bayer et al., we provide an explicit combinatorial construction of a shelling order, yielding a direct counting formula for the number of spheres in the wedge sum decomposition. † † footnotetext: 2020 Mathematics Subject Classification. 05C69, 05E45, 55P15, 57M15 † † footnotetext: Keywords and phrases. k -cut complex; shellable simplicial complex; hexagonal grid graph; homotopy type 1 Introduction Simplicial complexes arising from graph-based properties are well-studied objects in topological combinatorics. The books by Jonsson [ 14 ] and Kozlov [ 15 ] are excellent works in this regard. Simplicial complexes naturally occur at the intersection of various areas of mathematics. Among these, the interaction with commutative algebra is especially prominent, where these complexes appear via Stanley–Reisner theory (see, for instance, [ 6 , 7 , 12 , 13 , 16 , 17 ] ). For instance, this connection has been explored in detail in recent work of Bayer et al. (see [ 3 , 1 , 2 ] ). In 1990, Fröberg proved his celebrated theorem [ 9 , Theorem 1] concerning ideals generated by quadratic monomials. Subsequently, Eagon and Reiner [ 8 , Proposition 8] generalized Fröberg’s result using the Alexander dual of the clique complex \Delta(G) , denoted by \Delta_{2}(G) , whose facets correspond to complements of independent sets of size 2 . Motivated by this line of work, Bayer et al. recently introduced two classes of graph complexes: the total k -cut complexes and the k -cut complexes . In this article, we focus on k -cut complexes (see Definition 2.2 ). In their work, Bayer et al. established the shellability of k -cut complexes for a wide range of graph families. This includes trees, threshold graphs, cycles (for k\geq 3 ), complete multipartite graphs, squared paths, and grid graphs (specifically for the case k=3 ). Additionally, they conjectured that this shellability extends to grid graphs for general k\geq 1 , as well as to squared cycles when the number of vertices is sufficiently large relative to k\geq 2 . More recently, Chouhan et al. [ 5 ] studied the 3-cut complexes of squared cycle graphs and analyzed their shellability. Also, Chandrakar et al. in [ 4 ] , showed that the k -cut complex of \left(2\times n\right) -grid graphs are shellable when n\geq 3 and 3\leq k\leq 2n-2 . In this article, we study the shellability of the 3 -cut complex of hexagonal grid graphs (see Figure 1 ) and determine its homotopy type. We note that these results can be derived from [ 1 , Proposition 5.4] and [ 3 , Proposition 5.5] , where shellability is established using the notion of minimal forbidden subgraphs , and from [ 3 , Proposition 2.18] , where the homotopy type is computed via the Möbius function of the face lattice of the 3 -cut complex of a graph. While the general results of Bayer et al. yield both shellability and the homotopy type of this complex through the use of additional structural notions, we provide an independent proof using only the definition of shellability. Our approach is based solely on constructing an explicit shelling order and describing the associated spanning facets. It is worth noting that determining whether a simplicial complex is shellable is an NP -complete problem [ 10 ] . Consequently, finding an explicit shelling order, even for a complex already known to be shellable, is computationally difficult and often requires a detailed understanding of its combinatorial structure. In particular, we prove the following results, Theorem 1.1 ( Theorem 3.3 ) . For m,n\geq 1 , the simplicial complex \Delta_{3}\left(H_{1\times m\times n}\right) is shellable. The existence of a shelling order allows us to determine the homotopy type of the complex. This leads to the following theorem. Theorem 1.2 ( Theorem 4.1 ) . The 3-cut complex of H_{1\times m\times n} has the homotopy type of wedge of \psi_{m,n} many \left(2m+2n+2mn-4\right) -dimensional spheres, where, \psi_{m,n}=\binom{2m+2n+2mn-1}{2}-\left[\left(6m+2\right)n+(2m-4)\right]. In other words, \Delta_{3}\left(H_{1\times m\times n}\right)\simeq\bigvee\limits_{\psi_{m,n}}{\mathbb{S}^{\left(2m+2n+2mn-4\right)}}. Organization of the article: In Section 2 , we define the hexagonal grid graphs H_{1\times m\times n} for m,n\geq 1 and recall the necessary background on simplicial complexes, including the notions of shellability and spanning facets that will be used throughout the paper. In Section 3 , we introduce an explicit shelling order on the facets of the 3 -cut complex of H_{1\times m\times n} , defined via reverse lexicographic ordering, and prove that it indeed yields a shelling. Finally, in Section 4 , we characterize all spanning facets associated with this shelling order and use this description to determine the homotopy type of \Delta_{3}\left(H_{1\times m\times n}\right) . 2 Preliminaries In this section, we introduce the key concepts and results necessary for discussing the article. For k_{1},k_{2}\in\mathbb{N} , such that 1\leq k_{1}<k_{2} , we denote \displaystyle[k_{1}] \displaystyle=\left\{1,2,3,\dots,k_{1}\right\}; \displaystyle[k_{1},k_{2}] \displaystyle=\left\{k_{1},k_{1}+1,k_{1}+2,\dots,k_{2}\right\}. 2.1 Basics of graph theory A graph G is an ordered pair \left(V(G),E(G)\right) , where V(G) is the set of vertices and E(G)\subseteq\left\{\{u,v\}\mid u,v\in V(G),\ u\neq v\right\} is the set of edges. We use the notation uv to denote edge \{u,v\} . We define the open neighborhood of the vertex v in G , denoted by N_{G}(v) as, N_{G}\left(v\right)=\left\{u\in V(G)\ \middle|\ u\neq v\ \text{and}\ \left\{u,v\right\}\in E\left(G\right)\right\}. Similarly, the closed neighborhood of the vertex v in G , denoted by N_{G}[v] is defined as, N_{G}[v]=N_{G}(v)\sqcup\left\{v\right\}. When the underlying graph is clear from the context, we omit the subscript and write N(v) and N[v] to denote the open and closed neighborhoods of v , respectively. Let S be a subset of V(G) . The induced subgraph of G on S , denoted by G\left[S\right] , is the graph whose vertex set is S and whose edge set consists of all edges of G that have both vertices in S . We denote the induced subgraph G\left[V\left(G\right)\setminus H\right] by G\setminus H , where H\subset V\left(G\right) . We now proceed to formally define the hexagonal grid graphs. 2.2 Labelling of vertices in the general hexagonal grid graph. The hexagonal grid