On the Vertex Decomposability of r r -Independence Complexes of Trees

Rutuja Sawant · 2026

Read On the Vertex Decomposability of r r -Independence Complexes of Trees by Rutuja Sawant (2026) 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-2605-25150.txt.

Introduction

Rutuja Sawant proves that the r-independence complex of any tree is vertex decomposable, for every positive integer r. Here a set of vertices counts as r-independent when each connected piece of the subgraph it induces has at most r vertices. The family of all such sets forms a simplicial complex. Her recursive proof describes shedding vertices through rooted subtrees, settling a conjecture of Abdelmalek and coauthors and clarifying the topology of these complexes.

Catalog record

CREATORRutuja Sawant
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40613
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.25150

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Vertex Decomposability of r r -Independence Complexes of Trees Rutuja Sawant Abstract . Let G G be a graph and r ≥ 1 r\geq 1 . A vertex subset is r r -independent if every connected component of its induced subgraph has size at most r r . The family of all such subsets forms a simplicial complex, the r r -independence complex Ind r ​ ( G ) \mathrm{Ind}_{r}(G) , generalizing the classical independence complex. Recent work has focused on shellability and vertex decomposability of these complexes. For chordal graphs, Ind r ​ ( G ) \mathrm{Ind}_{r}(G) has the homotopy type of a wedge of spheres for all r r , and some chordal subfamilies are known where these complexes are not even sequentially Cohen–Macaulay. Thus, determining chordal graph classes and values of r r for which Ind r ​ ( G ) \mathrm{Ind}_{r}(G) is sequentially Cohen–Macaulay, shellable, or vertex decomposable remains an active area. Existing methods, based on chordal hypergraphs or special graph properties, do not extend to arbitrary chordal graphs. In this paper, we show that for every tree T T and every integer r ≥ 1 r\geq 1 , the complex Ind r ​ ( T ) \mathrm{Ind}_{r}(T) is vertex decomposable, resolving a conjecture [ 1 , Conjecture 3.15] of Abdelmalek et al. Our approach gives a structural description of shedding vertices via rooted subtrees and uses it to prove vertex decomposability recursively. 2020 Mathematics Subject Classification 05E45, 05C76, 55U10, 05C05. 1. Introduction Independence complexes have long formed an important interface between graph theory, combinatorial topology, and commutative algebra, with deep connections to Stanley-Reisner theory and related algebraic invariants [ 2 , 9 , 10 , 11 , 14 , 17 , 22 , 23 , 25 ] . A natural generalization, known as the r -independence complex, was introduced by Paolini and Salvetti [ 18 ] . For an integer r\geq 1 , a subset A\subseteq V(G) is called r -independent if every connected component of the induced subgraph G[A] has size at most r . The collection of all such subsets forms a simplicial complex, called the r -independence complex of G , denoted by \mathrm{Ind}_{r}(G) . When r=1 , this construction recovers the classical independence complex. Higher independence complexes have since attracted considerable interest because of their connections with domination parameters, homological connectivity, and hypergraph methods [ 7 , 8 , 12 ] . A central theme in the study of independence-type complexes is to understand when they satisfy strong combinatorial properties such as shellability and vertex decomposability. These notions are related through the implications \text{Vertex decomposable}\Rightarrow\text{Shellable}\Rightarrow\text{Sequentially Cohen-Macaulay}, see [ 15 ] . In particular, shellable complexes have the homotopy type of a wedge of spheres, although the converse need not hold. The notion of vertex decomposability was introduced by Provan and Billera [ 19 ] and later extended to non-pure complexes by Björner and Wachs [ 4 , 5 ] . In the classical case r=1 , Dochtermann and Engström [ 9 ] and Woodroofe [ 25 ] proved that if G is chordal, then \mathrm{Ind}(G) is vertex decomposable. These results naturally motivate the investigation of analogous structural properties for the higher independence complexes \mathrm{Ind}_{r}(G) . Motivated by this, Abdelmalek et al. [ 1 ] studied shellability and vertex decomposability of higher independence complexes through methods from the theory of chordal hypergraphs. Using a hypergraph associated to a graph G , they claimed that \mathrm{Ind}_{r}(T) is shellable for every tree T , and proved that \mathrm{Ind}_{r}(G) is vertex decomposable for caterpillar graphs. Their approach relied on Woodroofe’s result that the independence complex of a chordal hypergraph is shellable [ 24 ] . They also constructed chordal graphs whose higher independence complexes are not sequentially Cohen-Macaulay, showing that the behavior of \mathrm{Ind}_{r}(G) for r\geq 2 differs substantially from that of ordinary independence complexes. However, as later observed by Ghosh and Selvaraja [ 12 , Remark 4.2] , the required chordality assertion for the associated hypergraph fails for arbitrary trees. Consequently, the proof in Abdelmalek et al. does not establish shellability of \mathrm{Ind}_{r}(T) for all trees. These developments left open the question of whether higher independence complexes of trees possess stronger combinatorial properties. This was posed as a conjecture in [ 1 ] . Unlike the classical independence complex, higher independence complexes allow connected induced subgraphs of bounded size, making the recursive structure of links and deletions substantially more complicated. Moreover, the previously proposed hypergraph approach does not apply to arbitrary trees. The main result of this paper resolves the conjecture completely. Theorem 1.1 (Theorem 3.6 ) . Let T be a tree and let r\geq 1 . Then the r -independence complex \mathrm{Ind}_{r}(T) is vertex decomposable. Our proof gives a structural characterization of shedding vertices in \mathrm{Ind}_{r}(T) in terms of rooted subtrees of T . We further show that links with respect to connected induced subgraphs inherit compatible shedding vertices, allowing vertex decomposability to be established recursively without relying on hypergraph chordality techniques. Theorem 1.1 also has consequences for other graph complexes closely related to higher independence complexes. In particular, path-free complexes form an important class of simplicial complexes associated with graphs and have been studied extensively from combinatorial, algebraic, and topological viewpoints [ 6 , 3 , 13 , 20 ] . Recall that the t -path free complex of a graph G is the simplicial complex whose faces are subsets of vertices inducing no path on t vertices. Observe that a subset A\subseteq V(G) induces no path on three vertices if and only if every connected component of G[A] has size at most 2 . Consequently, the 3 -path free complex of G coincides with the 2 -independence complex \mathrm{Ind}_{2}(G) . As an immediate consequence of Theorem 1.1 , it follows that the 3 -path free complex of a tree is vertex decomposable. The paper is organized as follows. Section 2 recalls background on graphs, simplicial complexes, vertex decomposability, and higher independence complexes. Section 3 contains the proof of the main theorem. 2. Preliminaries In this section, we collect the definitions and preliminary results needed for the proof of the main theorem. We begin with basic notions from graph theory and rooted trees, then review simplicial complexes and vertex decomposability, and finally discuss properties of r -independence complexes that will be used throughout. 2.1. Graph theory. A (finite, simple) graph is a pair G=(V(G),E(G)) , where V(G) is a finite set of vertices and E(G)\subseteq\{\{u,v\}:u,v\in V(G),\,u\neq v\} is the edge set. If \{u,v\}\in E(G) , then u and v are said to be adjacent , and the edge \{u,v\} is said to be incident with both u and v . A graph H is a subgraph of G if V(H)\subseteq V(G) and E(H)\subseteq E(G) . For a subset A\subseteq V(G) , the induced subgraph G[A] is the graph with vertex set A and edge set E(G[A])=\{\{u,v\}\in E(G):u,v\in A\}. For A\subseteq V(G) , the deletion G\setminus A is the induced subgraph G[V(G)\setminus A], obtained by deleting all vertices of A together with all incident edges. If G_{1} and G_{2} have disjoint vertex sets, then their disjoint union G_{1}\sqcup G_{2} is the graph with vertex set V(G_{1})\sqcup V(G_{2}) and edge set

Read the complete text