arxiv: 2604.12606 · v1 · submitted 2026-04-14 · 🧮 math.CO · math.AT

Recognition: unknown

A recursive construction of an acyclic matching on the independence complex of a graph with a simplicial vertex

Sucharita Barik , Anupam Mondal , Sajal Mukherjee

Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:25 UTC · model grok-4.3

classification 🧮 math.CO math.AT

keywords independence complexacyclic matchingdiscrete Morse theorysimplicial vertexchordal graphshomotopy typegradient vector field

0 comments

The pith

A recursive construction yields an acyclic matching on the independence complex of any graph containing a simplicial vertex.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a recursive procedure to build an acyclic matching on the independence complex of a graph whenever it contains a simplicial vertex. The construction combines given acyclic matchings on the independence complexes of the graph minus the simplicial vertex and the graph minus its closed neighborhood. This yields an algorithmic determination of the homotopy type for the independence complexes of all chordal graphs and for a class of graphs that generalize comparability graphs of grid posets. The same method supplies a preprocessing step that can accelerate homology calculations even in cases where the homotopy type remains undetermined.

Core claim

We provide a recursive construction of an acyclic matching 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.

What carries the argument

The recursive gluing of acyclic matchings on the independence complexes of the deletion and the link of the simplicial vertex, which produces a new acyclic matching on the full complex.

Load-bearing premise

Acyclic matchings already exist on the independence complexes of the two proper subgraphs obtained by removing the simplicial vertex or its closed neighborhood, and the gluing step preserves acyclicity.

What would settle it

Take any small chordal graph with a simplicial vertex, such as the path on three vertices, apply the recursive construction explicitly, and check whether the resulting matching on the independence complex contains a cycle in its associated flow graph.

Figures

Figures reproduced from arXiv: 2604.12606 by Anupam Mondal, Sajal Mukherjee, Sucharita Barik.

**Figure 1.** Figure 1: A graph G ∈ Gm,n is represented by this grid diagram, where two vertices are adjacent if and only if they are reachable via a (north-east) lattice path. For instance, the region bounded by the solid line segments represents NG[x], for x ∈ Vi,j , and the dotted rectangles contain the non-neighbours of x. Theorem 3.8. For any G ∈ Gm,n, there is an acyclic matching M on I(G) such that all Mcritical simplices… view at source ↗

**Figure 2.** Figure 2: For u ∈ Vi,0, the solid rectangle represents the graph G − NG[u] ∈ Gi−1,n−1 with the vertex set i F−1 r=0 nF−1 s=0 V ′ r,s, where V ′ r,s = Vr,s+1, and for u ∈ Vm,j , the dotted rectangle represents the graph G − NG[u] ∈ Gm−1,n−j−1 with the vertex set mF−1 r=0 n−F j−1 s=0 V ′ r,s, where V ′ r,s = Vr,s+j+1. We construct an acyclic matching M on I(G) by using all such Mu, following the proof of Theorem 1.1. … view at source ↗

**Figure 3.** Figure 3: For i ∈ {0, 1, . . . , m − 1} and j ∈ {1, 2, . . . , n} the dotted rectangle represents the graph Gi,j . Let di,j := dim(I(Gi,j )) = min{i, n−j}. For ℓ ∈ {0, 1, . . . , di,j}, let c (ℓ) i,j denote the number of ℓ-dimensional critical simplices of I(Gi,j ) with respect to an acyclic matching M′ , constructed recursively in the proof of Theorem 3.8. In other words, c (ℓ) i,j = f M′ ℓ (I(Gi,j )). We provide a… view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a recursive construction for acyclic matchings on independence complexes of graphs with simplicial vertices, turning some prior homotopy results for chordal graphs into a step-by-step combinatorial procedure.

read the letter

The main point is a recursive way to build an acyclic matching on the independence complex of G when v is simplicial: take given acyclic matchings on the complexes of G-v and G-N[v], then combine them so that no alternating cycles appear. The simplicial condition blocks the crossings that would create problems, and the base cases like edgeless graphs are trivial. This is the new piece. Earlier work got the homotopy types for chordal graphs and certain grid-poset comparability graphs via heavier topological arguments; here the same types follow by repeated removal of simplicial vertices until the complex collapses or the critical cells are counted. The construction also gives a preprocessing step for homology even when the type is not obvious. The gluing argument is standard discrete-Morse territory once the simplicial property is in hand, but writing it out explicitly as a recursion for this family of complexes is useful and organizes the computations. The stress-test note lines up with the abstract: acyclicity holds because potential cycles would need to jump between the two sub-matchings in a way the graph forbids. No extra parameters or self-reference show up. If the full paper includes worked examples or a clear algorithm for applying the recursion, that strengthens the practical side. Minor soft spot is that the applications to the two graph families are then immediate from the existence of perfect elimination orders, so the paper is mostly the general tool plus the observation that it covers those cases. This is aimed at people working on discrete Morse theory for graph complexes or combinatorial homotopy of independence complexes. A reader who needs an algorithmic handle on these homotopy types or wants to compute homology via gradient fields will find a concrete reference. I would send it to peer review. The technique is grounded enough to be worth a detailed check and a place in the literature as a reference construction.

Referee Report

0 major / 3 minor

Summary. The paper provides a recursive construction of an acyclic matching on the independence complex of a graph G containing a simplicial vertex v, built from given acyclic matchings on the independence complexes of G−v and G−N[v]. The construction is applied to compute the homotopy types of independence complexes for chordal graphs and a class of graphs generalizing comparability graphs of grid posets, using discrete Morse theory in an algorithmic and combinatorial manner; some of these homotopy types were previously obtained via more advanced techniques. The method also yields a preprocessing framework for homology computation even when the full homotopy type is not immediately determined.

Significance. If the recursive construction and its acyclicity proof are correct, the result supplies a systematic, inductive way to obtain discrete Morse functions on independence complexes of chordal graphs and related families by repeated removal of simplicial vertices down to contractible base cases. This yields explicit homotopy types (often wedges of spheres) and critical-cell counts without relying on heavy homotopy-theoretic machinery, while also providing a practical reduction step for computational homology. The approach is parameter-free and directly combinatorial, strengthening the toolkit for applying discrete Morse theory to graph complexes.

minor comments (3)

The abstract and introduction would benefit from an explicit small example (e.g., a path or tree on 4–5 vertices) that walks through one recursive step, showing the two sub-matchings and the resulting matching on the full complex.
Base cases (edgeless graphs and single-vertex graphs) are mentioned as contractible or empty; a short dedicated paragraph or lemma verifying that the trivial matching is acyclic on these complexes would make the induction fully self-contained.
Notation for the subgraphs (G−v versus G−N[v]) and for the glued matching should be introduced once in a preliminary section and used consistently; occasional shifts between “closed neighborhood” and “link” terminology could be unified.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. We are pleased that the referee recognizes the value of the recursive construction for obtaining acyclic matchings on independence complexes and its applications to determining homotopy types of chordal graphs and generalized comparability graphs via discrete Morse theory in a combinatorial manner.

Circularity Check

0 steps flagged

No significant circularity in the recursive construction

full rationale

The paper presents a recursive construction of an acyclic matching on the independence complex of a graph with a simplicial vertex, built directly from given acyclic matchings on the independence complexes of the proper subgraphs G-v and G-N[v]. Acyclicity is preserved by the simplicial vertex property, which prevents crossing edges that could create alternating cycles between the two pieces; base cases (edgeless graphs, isolated vertices) admit the trivial matching and are contractible. The method is applied inductively to chordal graphs and grid-poset comparability graphs by repeated simplicial elimination until collapse. No step equates a derived quantity to its input by definition, renames a fitted parameter as a prediction, or relies on a load-bearing self-citation whose content is unverified; the derivation is self-contained and independent.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard background from discrete Morse theory and simplicial complexes; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)

standard math An acyclic matching on a simplicial complex corresponds to a discrete Morse function whose critical cells determine the homotopy type.
Core equivalence in discrete Morse theory, used implicitly to obtain homotopy types from the constructed matching.
domain assumption The independence complex of a graph is a simplicial complex whose faces are the independent sets.
Standard definition in the field, required for the statement to make sense.

pith-pipeline@v0.9.0 · 5419 in / 1356 out tokens · 34476 ms · 2026-05-10T15:25:02.489340+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 17 canonical work pages

[1]

Jonathan A. Barmak. Star clusters in independence complexes of graphs.Advances in Mathematics, 241:33–57, 2013. URL:https://doi.org/10.1016/j.aim.2013.03.016

work page doi:10.1016/j.aim.2013.03.016 2013
[2]

Topological methods.Handbook of combinatorics, 2:1819–1872, 1995

Anders Björner. Topological methods.Handbook of combinatorics, 2:1819–1872, 1995

1995
[3]

Homotopy properties of greedoids

Anders Björner, Bernhard Korte, and László Lovász. Homotopy properties of greedoids. Advances in Applied Mathematics, 6(4):447–494, 1985. URL:https://doi.org/10.1016/ 0196-8858(85)90021-1

1985
[4]

Cohen.A course in simple-homotopy theory

Marshall M. Cohen.A course in simple-homotopy theory. Springer Science & Business Media, 2012

2012
[5]

Distance r-domination number and r-independence complexes of graphs.Eur

Priyavrat Deshpande, Samir Shukla, and Anurag Singh. Distance r-domination number and r-independence complexes of graphs.Eur. J. Comb., 102(103508):103508, May 2022. URL:https://doi.org/10.1016/j.ejc.2022.103508

work page doi:10.1016/j.ejc.2022.103508 2022
[6]

Gabriel A. Dirac. On rigid circuit graphs.Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25:71–76, 1961. URL:https://doi.org/10.1007/BF02992776

work page doi:10.1007/bf02992776 1961
[7]

Gonzalez

Ömer Eğecioğlu and Teofilo F. Gonzalez. A computationally intractable problem on sim- plicial complexes.Computational Geometry, 6(2):85–98, 1996. URL:https://doi.org/ 10.1016/0925-7721(95)00015-1

work page doi:10.1016/0925-7721(95)00015-1 1996
[8]

The topology of the independence complex.Euro- pean Journal of Combinatorics, 27(6):906–923, 2006

Richard Ehrenborg and Gábor Hetyei. The topology of the independence complex.Euro- pean Journal of Combinatorics, 27(6):906–923, 2006. URL:https://doi.org/10.1016/ j.ejc.2005.04.010

2006
[9]

Independence complexes of claw-free graphs.European Journal of Combinatorics, 29(1):234–241, 2008

Alexander Engström. Independence complexes of claw-free graphs.European Journal of Combinatorics, 29(1):234–241, 2008. URL:https://doi.org/10.1016/j.ejc.2006.09. 007

work page doi:10.1016/j.ejc.2006.09 2008
[10]

Complexes of directed trees and independence complexes.Discrete Mathematics, 309(10):3299–3309, 2009

Alexander Engström. Complexes of directed trees and independence complexes.Discrete Mathematics, 309(10):3299–3309, 2009. URL:https://doi.org/10.1016/j.disc.2008. 09.033

work page doi:10.1016/j.disc.2008 2009
[11]

Morse theory for cell complexes.Advances in Mathematics, 134:90–145,

Robin Forman. Morse theory for cell complexes.Advances in Mathematics, 134:90–145,
[12]

URL:https://doi.org/10.1006/aima.1997.1650

work page doi:10.1006/aima.1997.1650 1997
[13]

A user’s guide to discrete Morse theory.Séminaire Lotharingien de Com- binatoire [electronic only], 48:B48c–35, 2002

Robin Forman. A user’s guide to discrete Morse theory.Séminaire Lotharingien de Com- binatoire [electronic only], 48:B48c–35, 2002

2002
[14]

Fulkerson and Oliver A

Delbert R. Fulkerson and Oliver A. Gross. Incidence matrices and interval graphs.Pacific Journal of Mathematics, 15:835–855, 1965

1965
[15]

Combinatorial realization of the thom-smale complex via discrete Morse theory.Annali della Scuola Normale Superiore di Pisa-Classe di Scienze, 9(2):229–252,

Étienne Gallais. Combinatorial realization of the thom-smale complex via discrete Morse theory.Annali della Scuola Normale Superiore di Pisa-Classe di Scienze, 9(2):229–252,
[16]

URL:https://doi.org/10.2422/2036-2145.2010.2.01. 15

work page doi:10.2422/2036-2145.2010.2.01 2036
[17]

Discrete Morse theoretic algorithms for computing homology of complexes and maps.Foundations of Computational Mathematics, 14(1):151–184, 2014

Shaun Harker, Konstantin Mischaikow, Marian Mrozek, and Vidit Nanda. Discrete Morse theoretic algorithms for computing homology of complexes and maps.Foundations of Computational Mathematics, 14(1):151–184, 2014. URL:https://doi.org/10.1007/ s10208-013-9145-0

2014
[18]

Michael Joswig and Marc E. Pfetsch. Computing optimal Morse matchings.SIAM Journal on Discrete Mathematics, 20(1):11–25, 2006. URL:https://doi.org/10.1137/ S0895480104445885

2006
[19]

Homotopy types of independence complexes of forests.Contributions to Discrete Mathematics, 5(2), 2010

Kazuhiro Kawamura. Homotopy types of independence complexes of forests.Contributions to Discrete Mathematics, 5(2), 2010. URL:https://doi.org/10.55016/ojs/cdm.v5i2. 62064

work page doi:10.55016/ojs/cdm.v5i2 2010
[20]

Independence complexes of chordal graphs.Discrete mathematics, 310(15-16):2204–2211, 2010

Kazuhiro Kawamura. Independence complexes of chordal graphs.Discrete mathematics, 310(15-16):2204–2211, 2010. URL:https://doi.org/10.1016/j.disc.2010.04.021

work page doi:10.1016/j.disc.2010.04.021 2010
[21]

Kozlov.Organized collapse: an introduction to discrete Morse theory, volume

Dmitry N. Kozlov.Organized collapse: an introduction to discrete Morse theory, volume
[22]

American mathematical society, 2021

2021
[23]

Toward optimality in discrete Morse theory.Experimental Mathematics, 12, 01 2003

Thomas Lewiner, Hélio Lopes, and Geovan Tavares. Toward optimality in discrete Morse theory.Experimental Mathematics, 12, 01 2003. URL:https://doi.org/10.1080/ 10586458.2003.10504498

work page arXiv 2003
[24]

Morse theory for filtrations and efficient compu- tation of persistent homology.Discrete & Computational Geometry, 50(2):330–353, 2013

Konstantin Mischaikow and Vidit Nanda. Morse theory for filtrations and efficient compu- tation of persistent homology.Discrete & Computational Geometry, 50(2):330–353, 2013. URL:https://doi.org/10.1007/s00454-013-9529-6

work page doi:10.1007/s00454-013-9529-6 2013
[25]

Topology of matching complexes of complete graphs via discrete Morse theory.Discrete Mathematics & Theoretical Computer Science, 26:3, 2024

Anupam Mondal, Sajal Mukherjee, and Kuldeep Saha. Topology of matching complexes of complete graphs via discrete Morse theory.Discrete Mathematics & Theoretical Computer Science, 26:3, 2024. URL:https://doi.org/10.46298/dmtcs.12887

work page doi:10.46298/dmtcs.12887 2024
[26]

Pramanik

Anupam Mondal and Pritam C. Pramanik. A note on an application of discrete Morse the- oretic techniques on the complex of disconnected graphs.Examples and Counterexamples, 7:100174, 2025. URL:https://doi.org/10.1016/j.exco.2025.100174

work page doi:10.1016/j.exco.2025.100174 2025
[27]

Nandini Nilakantan and Ramesh P. Panda. Independence complexes of power graphs of cyclic groups of orderpnqm.Journal of Algebra and Its Applications, page 2750109, 2025. URL:https://doi.org/10.1142/S021949882750109X

work page doi:10.1142/s021949882750109x 2025
[28]

Donald J. Rose, R. Endre Tarjan, and George S. Lueker. Algorithmic aspects of vertex elimination on graphs.SIAM Journal on computing, 5(2):266–283, 1976. URL:https: //doi.org/10.1137/0205021

work page doi:10.1137/0205021 1976
[29]

Homotopy type of independence com- plexes of certain families of graphs.Contributions to Discrete Mathematics, 16(3):74–92, December 2021

Samir Shukla, Shuchita Goyal, and Anurag Singh. Homotopy type of independence com- plexes of certain families of graphs.Contributions to Discrete Mathematics, 16(3):74–92, December 2021. URL:https://doi.org/10.55016/ojs/cdm.v16i3.71284. 16

work page doi:10.55016/ojs/cdm.v16i3.71284 2021
[30]

Vassiliev

Victor A. Vassiliev. Complexes of connected graphs. InThe Gelfand Mathematical Sem- inars, 1990–1992, pages 223–235. Springer, 1993. URL:https://doi.org/10.1007/ 978-1-4612-0345-2_15. 17

1990