A recursive construction of an acyclic matching on the independence complex of a graph with a simplicial vertex
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911592146272256 |
|---|---|
| author | Barik, Sucharita Mondal, Anupam Mukherjee, Sajal |
| author_facet | Barik, Sucharita Mondal, Anupam Mukherjee, Sajal |
| contents | We provide a recursive construction of an acyclic matching (also known as a gradient vector field, an equivalent notion to a discrete Morse function) on the independence complex of a graph with a simplicial vertex using given acyclic matchings on the independence complexes of specific subgraphs. As an application, we determine the homotopy type of the independence complexes of the family of chordal graphs and of a class of graphs generalising the comparability graphs of grid posets in an algorithmic and combinatorial manner via discrete Morse theory, some of which were previously obtained by sophisticated homotopy theoretic techniques. Even when the homotopy type is not easily determinable, our construction may be applied to obtain a pre-processing framework for efficient homology computation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_12606 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A recursive construction of an acyclic matching on the independence complex of a graph with a simplicial vertex Barik, Sucharita Mondal, Anupam Mukherjee, Sajal Combinatorics Algebraic Topology 57Q70, 05E45, 05C69, 55P10 We provide a recursive construction of an acyclic matching (also known as a gradient vector field, an equivalent notion to a discrete Morse function) on the independence complex of a graph with a simplicial vertex using given acyclic matchings on the independence complexes of specific subgraphs. As an application, we determine the homotopy type of the independence complexes of the family of chordal graphs and of a class of graphs generalising the comparability graphs of grid posets in an algorithmic and combinatorial manner via discrete Morse theory, some of which were previously obtained by sophisticated homotopy theoretic techniques. Even when the homotopy type is not easily determinable, our construction may be applied to obtain a pre-processing framework for efficient homology computation. |
| title | A recursive construction of an acyclic matching on the independence complex of a graph with a simplicial vertex |
| topic | Combinatorics Algebraic Topology 57Q70, 05E45, 05C69, 55P10 |
| url | https://arxiv.org/abs/2604.12606 |