1 Introduction↩︎

Discrete Morse theory, introduced by Forman [1], provides a combinatorial framework for simplifying cell complexes while preserving their homotopy type. In this framework, a discrete gradient vector field on a finite cell complex can be described as an acyclic matching on its face poset, and the unmatched cells play the role of critical cells. Much of the classical theory, as well as many algorithmic applications, focuses on finding matchings with as few critical cells as possible. This optimisation problem is difficult in general: finding an optimal discrete Morse matching is NP-hard [2], [3].

Beyond the search for a single optimal matching, the collection of all acyclic matchings on a fixed complex has also been studied from several viewpoints. For example, the Chari–Joswig complex [4] organises acyclic matchings into a simplicial complex, and our previous works have investigated birth–death phenomena among discrete Morse functions [5], [6]. These approaches emphasise the structure of the space of discrete Morse functions, as well as the ways in which such functions are connected or transformed into one another.

The aim of the present paper is different and complementary. Our contribution is not the mere consideration of all acyclic matchings, but rather the introduction and study of a compact enumerative invariant that records their critical-vector distribution. More precisely, for a finite simplicial complex \(K\), we associate to the set of all acyclic matchings on the face poset \(P(K)\) a generating polynomial whose monomials encode the numbers of critical simplices in each dimension. This polynomial packages the ensemble of discrete Morse matchings into a single algebraic object, which we study as a combinatorial invariant of \(K\).

Concretely, let \(K\) be a finite simplicial complex of dimension \(d\). Each acyclic matching \(M\) on the face poset \(P(K)\) determines a Morse vector \(c(M)=(c_0(M),\ldots,c_d(M)),\) where \(c_i(M)\) denotes the number of unmatched, or critical, \(i\)-simplices.

The polynomial \(\mathcal{ME}_K\) is finite, has non-negative integer coefficients, and is an isomorphism invariant of simplicial complexes. It records not only which Morse vectors occur on \(K\), but also their multiplicities. Thus \(\mathcal{ME}_K\) refines the usual optimisation problem in discrete Morse theory, that is, instead of retaining only the minimum possible number of critical cells, it keeps track of the full distribution of critical cells among all acyclic matchings.

Our results centre on three main theorems.

Main Theorem I: The Laplacian Formula (Theorem 10). For a connected graph \(G\) with \(n\) vertices, \(m\) edges, and Laplacian \(L_G\) with eigenvalues \(0=\lambda_1\leq\cdots\leq\lambda_n\): \[\mathcal{ME}_G(z_0,z_1) = z_1^{m-n}\det(z_0z_1\,I_n + L_G) = z_1^{m-n}\prod_{i=1}^n(z_0z_1 + \lambda_i).\] This identifies \(\mathcal{ME}_G\) as a complete Laplacian spectral invariant and yields incomparability with the Tutte polynomial \(T_G\): neither \(\mathcal{ME}_G\) nor \(T_G\) determines the other.

Main Theorem II: The Top-Face Recursion (Theorem 16). Let \(\sigma\) be a \(d\)-simplex whose boundary is contained in \(K\), and set \(K'=K\cup\{\sigma\}\). Then, \[\mathcal{ME}_{K\cup\{\sigma\}} \;=\; z_d\cdot\mathcal{ME}_K \;+\; \sum_{\tau\prec\sigma}\widetilde{\mathcal{ME}}_{(K',\sigma,\tau)},\] where \(\widetilde{\mathcal{ME}}_{(K',\sigma,\tau)}\) counts acyclic matchings on \(P(K')\setminus\{\sigma,\tau\}\) whose lift remains acyclic. Equivalently, \[\widetilde{\mathcal{ME}}_{(K',\sigma,\tau)} =\mathcal{ME}_{P(K')\setminus\{\sigma,\tau\}}-F(K,\sigma,\tau).\] The correction term \(F\) is not a black box. It vanishes exactly under the incidence-separation criterion of Theorem 17, and has its leading obstruction term controlled by Theorem 18. Thus, the graph bridge recursion (Theorem 7) is the one-dimensional shadow of the higher-dimensional Top-Face Recursion (Theorem 16). Also, the analogy with Tutte deletion-contraction is explained in Remark 20.

Main Theorem III: \(\Phi(G)\) as a fine graph invariant (Theorems 32, 33, 34). The independence ME polynomial \(\Phi(G):=\mathcal{ME}_{\mathop{\mathrm{Ind}}(G)}\) fits into a strict hierarchy with the one-dimensional graph invariant \(\mathcal{ME}_G\), that is, \(\Phi(G)\) determines \(\mathcal{ME}_G\), and the determination is strict. More precisely:

The coefficient \([z_0]\Phi(G)\) gives an additional collapse-level interpretation: it counts collapsing matchings of \(\mathop{\mathrm{Ind}}(G)\) when such matchings exist.

The paper is organised as follows. Section 2 develops the Forest Expansion and Compositional Lemma. Sections 2.1–3 give exact formulas for paths and cycles and establish the Bridge Recursion. Section 4 proves Main Theorem I and its spectral consequences. Section 5 establishes Main Theorem II with the Collapsibility Criterion and separation theorems. Section 6 applies the Top-Face Recursion to perfect and optimal discrete Morse vectors. Section 7 proves Main Theorem III. Section 8 collects open problems.

2 The Forest Expansion↩︎

We recall the basic notation for acyclic matchings and discrete Morse theory. The face poset \(P(K)\) of a finite simplicial complex \(K\) is the partially ordered set of all simplices of \(K\), ordered by inclusion. Its covering relations are precisely the pairs \(\sigma\prec\tau\) with \(\sigma\subset\tau\) and \(\dim\tau=\dim\sigma+1\).

An acyclic matching on \(P(K)\) is a collection \(M\) of covering pairs \((\sigma,\tau)\) such that each simplex of \(K\) appears in at most one pair and such that the Hasse diagram, after reversing the matched edges, contains no directed cycle  [1]. The simplices not appearing in any pair of \(M\) are called critical. We write \(c_i(M)\) for the number of critical \(i\)-simplices. Thus every acyclic matching determines a Morse vector \[c(M)=(c_0(M),\ldots,c_d(M)).\] By Forman’s theorem [1], if \(K\) has dimension \(d\), then \(K\) is homotopy equivalent to a CW complex with exactly \(c_i(M)\) cells of dimension \(i\). In particular, the Morse vector satisfies the Morse inequalities \(c_i(M)\geq \beta_i(K).\) A matching for which \(c_i(M)=\beta_i(K)\) for all \(i\) is called perfect; such matchings need not exist.

The set of all acyclic matchings on \(P(K)\) will be denoted by \(\mathcal{A}(K)\). As defined in the introduction, the Morse ensemble polynomial is \[\mathcal{ME}_K(z_0,\ldots,z_d) = \sum_{M\in\mathcal{A}(K)} \prod_{i=0}^d z_i^{c_i(M)},\] where \(\mathcal{A}(K)\) is the set of all acyclic matchings on \(P(K)\). The polynomial \(\mathcal{ME}_K\) records the Morse vectors of all acyclic matchings, with multiplicities. The set \(\mathcal{A}(K)\) also has a natural simplicial-complex structure. More precisely, following Kozlov [7], Chari and Joswig [4] showed that acyclic matchings on \(P(K)\) form the simplices of the Chari–Joswig complex \(\mathfrak{M}(K)\). In this sense, \(\mathcal{ME}_K\) refines the ordinary \(f\)-polynomial of \(\mathfrak{M}(K)\) by recording the dimensions of critical simplices; see Section 5.5.

We first record a basic multiplicativity property.

We next specialize to graphs. Let \(G=(V,E)\) be a connected graph with \(|V|=n\) and \(|E|=m\), viewed as a one-dimensional simplicial complex. Then \(P(G)\) has elements \(V\cup E\), ordered by \(v<e\) whenever the vertex \(v\) is incident to the edge \(e\). Hence an acyclic matching on \(P(G)\) is a collection of vertex–edge pairs \((v,e)\), with \(v\in e\), satisfying the matching and acyclicity conditions above.

For graphs, the Chari–Joswig complex admits a concrete interpretation. It coincides with the complex of rooted spanning forests. Equivalently, an acyclic matching on \(P(G)\) can be described by choosing a forest support \(F\subseteq G\) together with a root in each connected component of \(F\). The bijection underlying this description is implicit in Kozlov [7] and Chari–Joswig [4]. For later use in the proof of the Laplacian formula, we state it below as an explicit counting formula.

The following is a fundamental fact in discrete Morse theory.

For a forest \(F\subseteq E\), let \(a(F)\) denote the number of acyclic matchings whose matched edges are exactly \(F\). Since the unmatched vertices number \(n-|F|\) and unmatched edges number \(m-|F|\), summing over all possible forests gives the following equality.

Proposition 2 reduces computing \(\mathcal{ME}_G\) to counting valid orientations of each forest \(F\). A valid orientation of \(F\) directs each edge such that every vertex receives at most one incoming edge, equivalently, each tree component \(T\) of \(F\) is rooted at its unique escape vertex with all edges directed away from it. The following lemma gives the exact count.

Note that the identity \(a(T)=|V(T)|\) is shape-independent. For example, the path graph \(P_\ell\) and the star \(K_{1,\ell-1}\) both have \(a=\ell\), despite having entirely different structures.

Combining Proposition 2 with Lemma 2 gives an explicit formula for the Morse ensemble on graphs.

2.1 Exact Formulas for Paths and Cycles↩︎

As a first application of the forest expansion, we compute \(\mathcal{ME}\) for paths and cycles, recovering Fibonacci and Lucas numbers as special cases by evaluating at \(z_0=z_1=1\).

Let \(P_n\) denote the path on \(n\) vertices. Since every subgraph of \(P_n\) is a forest, a \(k\)-component spanning forest corresponds to a composition \[\ell_1+\cdots+\ell_k = n,\] where \(\ell_i \geq 1\), with compositional weight \(\prod\ell_i\) and Morse vector \((c_0, c_1) = (k, k-1)\).

Next let \(C_n\) denote the cyclic graph on \(n\) vertices. A spanning forest of \(C_n\) with \(k\) connected components is obtained by deleting \(k\) edges from the cycle, leaving \(k\) path arcs of lengths summing to \(n\), with Morse vector \((k, k)\).

Evaluating at \(z_0=z_1=1\) recovers classical combinatorial identities.

These also follow from the Laplacian Formula via \(|\mathcal{A}(G)| = \prod_i(1+\lambda_i)\) and the known spectra of \(P_n\) and \(C_n\).

3 The Bridge Recursion↩︎

Next, we derive a deletion-type recursion for bridge edges, analogous in spirit to the Tutte deletion-contraction formula (though as we note in Remark 8, no such formula holds for non-bridge edges, reflecting a fundamental difference between \(\mathcal{ME}_G\) and \(T_G\)).

4 The Laplacian Formula and Spectral Theory of \(\mathcal{ME}_G\)↩︎

We now prove the first main result, which expresses \(\mathcal{ME}_G\) in terms of the graph Laplacian and yields a complete spectral dictionary for acyclic matchings on graphs. The key bridge between the Forest Expansion and spectral theory is the Matrix-Forest Theorem.

Combining the Forest Expansion with the Matrix-Forest Theorem gives the central result of this section.

For trees (\(m=n-1\)), \(z_1^{m-n}=z_1^{-1}\). Since \(\lambda_1=0\) is always a Laplacian eigenvalue, \(\det(z_0 z_1\,I+L_G)\) is divisible by \(z_0 z_1\) (hence by \(z_1\)), making \(\mathcal{ME}_G\) a polynomial with nonnegative integer exponents.

Setting \(z_0=z_1=1\) in Theorem 10 gives the immediate spectral count \[\label{eq:spectral-count} |\mathcal{A}(G)|=\det(I_n+L_G)=\prod_{i=1}^n(1+\lambda_i(G)).\tag{2}\]

4.1 Spectral coefficients dictionary↩︎

Recall that the \(k\)-th elementary symmetric polynomial of \(n\) variables is \[e_k(x_1,\ldots,x_n) = \sum_{1\leq i_1<\cdots<i_k\leq n}x_{i_1}\cdots x_{i_k},\] such that \[\prod_{i=1}^n(t+x_i)=\sum_{k=0}^n e_{n-k}\,t^k.\]

Equation 3 gives a dictionary between the ME polynomial and the Laplacian spectrum as follows. In particular, \[\begin{align} j=n:&\quad [z_0^nz_1^m]\mathcal{ME}_G = e_0 = 1 &\text{(trivial matching)},\\ j=n-1:&\quad [z_0^{n-1}z_1^{m-1}]\mathcal{ME}_G = e_1 = \textstyle\sum_i\lambda_i = \mathrm{tr}(L_G) = 2m &\text{(degree sum)},\\ j=1:&\quad [z_0z_1^{m-n+1}]\mathcal{ME}_G = e_{n-1} = n\tau(G) &\text{(Matrix-Tree Theorem)}. \end{align}\]

The \(j=n-1\) case has a direct combinatorial interpretation. There are exactly \(2m\) single-pair acyclic matchings (one pair \((v,e)\) for each of the two orientations of each edge \(e\)), and this equals \(e_1=\mathrm{tr}(L_G)=2m\). More generally, combining Corollary 1 with the Forest Expansion gives the rooted-forest dictionary \[\label{eq:rooted-forest-dictionary} \bigl[z_0^{\,j}z_1^{m-n+j}\bigr]\mathcal{ME}_G = \sum_{\substack{F\in\mathcal{F}(G)\\ c(F)=j}} \prod_{T\in\pi_0(F)} |V(T)|.\tag{4}\] Thus the \(j\)-th coefficient counts rooted spanning forests with \(j\) components, where each tree component is rooted independently. In particular, the case \(j=1\) gives rooted spanning trees, and the case \(j=n\) is the trivial matching.

At the opposite end, the coefficient with \(j=n-2\) counts two-pair acyclic matchings. Since any two disjoint primitive pairs are acyclic, we obtain the explicit degree formula \[\label{eq:two-pair-coefficient} \bigl[z_0^{n-2}z_1^{m-2}\bigr]\mathcal{ME}_G = \binom{2m}{2}-m- \sum_{v\in V}\binom{\deg(v)}{2}.\tag{5}\] Indeed, one first chooses two oriented incidences among the \(2m\) possible vertex–edge pairs, and subtracts the choices sharing the same edge or the same vertex. Equivalently, 5 gives a matching-theoretic interpretation of \(e_2(\lambda_1,\ldots,\lambda_n)\). Thus \(\mathcal{ME}_G\) simultaneously encodes the rooted spanning forest counts by number of components, the near-trivial matching counts, and the complete Laplacian spectrum.

A consequence of Corollary 1 is that \(\mathcal{ME}_G\) has full support: along the antidiagonal forced by the Euler relation, every monomial appears.

The Laplacian Formula also gives explicit formulas for graphs built by Cartesian products, since the Laplacian of \(G_1\square G_2\) is \(L_1\otimes I_{n_2}+I_{n_1}\otimes L_2\) with eigenvalues \(\{\lambda_i+\mu_j\}\).

4.2 Spectral identities and examples↩︎

The Laplacian eigenvalues of \(P_n\) and \(C_n\) are \(\lambda_k^{P}=2-2\cos(k\pi/n)\) and \(\lambda_k^{C}=2-2\cos(2\pi k/n)\). Combining with \(|\mathcal{A}(G)|=\prod_i(1+\lambda_i)\) and Theorem 6 gives the spectral identities as follows.

For the complete graphs \(K_n\), the eigenvalues are \(0\) and \(n\) (with multiplicity \(n-1\)), recovering the classical count of rooted spanning forests [11].

Table 1 summarises \(\mathcal{ME}_G\) for fundamental graphs.

These examples illustrate the agreement between combinatorial counts of acyclic matchings and spectral formulas derived from the Laplacian.

4.3 Comparison with the Tutte polynomial↩︎

\(\mathcal{ME}_G\) is a Laplacian-spectral invariant, while \(T_G\) is a cycle-matroid invariant. The following explicit witnesses show that neither invariant determines the other.

The failure of an ordinary graph-theoretic deletion-contraction formula for \(\mathcal{ME}_G\) is explained by the Top-Face Recursion in Section 5: for non-bridge edges, lifting matchings from the contracted face posets may create directed cycles, and the resulting overcount is measured by the correction term \(F(K,\sigma,\tau)\).

5 Support and Top-Face Recursion↩︎

For a simplicial complex \(K\) of dimension \(d\geq 2\), \(\mathcal{ME}_K\) records matching data in all dimensions and is no longer governed solely by the one-skeleton. Beyond the graph case, two natural questions arise: (a) which monomials can appear in \(\mathcal{ME}_K\) (the support question), and (b) how does \(\mathcal{ME}_K\) change when we attach a top-dimensional simplex (the recursive structure)?

Forman’s strong Morse inequalities give necessary constraints on the support. The main part of this section develops a deletion-contraction-style recursion for \(\mathcal{ME}_K\) under the attachment of a top-dimensional simplex. The key new feature, absent for bridge edges in graphs, is a lift obstruction measured by a correction term. \(T_{\mathrm{sk}_1(K)}\).

5.1 Support constraints beyond graphs↩︎

For connected graphs, Corollary 2 shows that the support is as large as possible once the Euler relation is imposed: every lattice point on the antidiagonal \(a_1-a_0=m-n\) with \(1\leq a_0\leq n\) occurs in \(\mathop{\mathrm{supp}}(\mathcal{ME}_G)\).

For higher-dimensional complexes the support can be strictly smaller, and the gap has topological content; we postpone an example to Example 22 below, where it appears naturally alongside the Collapsibility Criterion.

5.2 The Top-Face Recursion↩︎

5.3 The non-liftable correction term↩︎

5.4 Separation from graph-level invariants↩︎

The mechanism behind the proof is general. Attaching a top-dimensional simplex introduces new contraction terms in the Top-Face Recursion, which can create monomials not visible from the one-skeleton. An infinite family of separating pairs follows by disjoint union; see Proposition 24 below.

The graphs \(G_1,G_2\) above share the same rank function on edge subsets, i.e.they have isomorphic cycle matroids; by Whitney’s theorem [14] they are therefore related by a sequence of \(2\)-isomorphism operations. Such operations preserve \(T_G\) and triangle counts but can alter the combinatorial structure of \(K_4\)-subgraphs and higher cliques. \(\mathcal{ME}_{\Delta(G)}\) sees this change while \(T_G\) does not.

5.5 The Morse complex and Stanley–Reisner interpretation↩︎

The Chari–Joswig complex of discrete Morse matchings \(\mathfrak{M}(K)\) [4] has vertices the primitive vector fields on \(K\) and \(k\)-simplices the acyclic matchings of cardinality \(k+1\), with top-dimensional facets corresponding to optimal Morse matchings [15], [16]. \(\mathcal{ME}_K\) is the critical-vector refinement of the matching generating function of \(\mathfrak{M}(K)\): substituting \(z_i=t\) for all \(i\) gives \[\mathcal{ME}_K(t,\ldots,t) = t^{|K|} + t^{|K|-2}\cdot f_{\mathfrak{M}(K)}(t^{-2}),\] so \(\mathcal{ME}_K\) recovers the \(f\)-vector of \(\mathfrak{M}(K)\) after specialisation, while distinguishing matchings of the same cardinality with different critical vectors. Equivalently, in terms of the multigraded Stanley–Reisner face enumerator \(F_{\mathfrak{M}(K)}\) (with vertex \((\sigma^i,\tau^{i+1})\) of multidegree \(e_i+e_{i+1}\)), \[\label{eq:SR-bridge} \mathcal{ME}_K(z_0,\ldots,z_d) = \left(\prod_{i=0}^d z_i^{f_i(K)}\right) F_{\mathfrak{M}(K)}\bigl(u_{(\sigma^i,\tau^{i+1})}=(z_i z_{i+1})^{-1}\bigr).\tag{6}\] In the collapsible case, \([z_0]\mathcal{ME}_K\) counts those facets of \(\mathfrak{M}(K)\) corresponding to matchings with a single critical vertex. More generally, the Betti coefficient \(p_\Bbbk(K)\) counts the faces of \(\mathfrak{M}(K)\) whose dimension-weighted critical vector is \(\beta_\Bbbk(K)\).

6 Perfect Coefficients and Reduction Certificates↩︎

The Top-Face Recursion of Section 5 gives an exact recursion for the full Morse ensemble polynomial. In this section we extract from it the coefficient corresponding to the Betti vector. This coefficient counts perfect discrete Morse matchings, and the recursion gives a birth–death framework for studying its non-vanishing. Perfect discrete Morse functions have been studied from several viewpoints, including two-dimensional complexes, tight complexes and polytopal manifolds, and optimal Morse vectors [17]–[19]. Our purpose here is different: we do not give a general efficient decision algorithm for perfectness. Instead, we translate perfectness into a distinguished coefficient of \(\mathcal{ME}_K\), derive its Top-Face Recursion, and give reduction-theoretic certificates for the non-vanishing of this coefficient.

6.1 Perfect coefficients↩︎

Throughout this section, Betti numbers are taken over a fixed field \(\Bbbk\). We write \[\beta_\Bbbk(K) = (\beta_0(K;\Bbbk),\ldots,\beta_d(K;\Bbbk)), \qquad z^{\beta_\Bbbk(K)} = \prod_i z_i^{\beta_i(K;\Bbbk)}.\] An acyclic matching on \(P(K)\) is called perfect over \(\Bbbk\) if its critical vector is equal to \(\beta_\Bbbk(K)\). We define the perfect coefficient \[p_\Bbbk(K) := [z^{\beta_\Bbbk(K)}]\mathcal{ME}_K.\] Thus \(p_\Bbbk(K)\) counts the acyclic matchings that are perfect over \(\Bbbk\); in particular, \(p_\Bbbk(K)>0\) if and only if \(K\) admits a perfect discrete Morse matching over \(\Bbbk\).

The recursion separates naturally according to the homological effect of attaching the top simplex \(\sigma\).

Combining the death step with the incidence-separation theorem gives a usable obstruction-free certificate.

6.2 Perfect reduction sequences↩︎

The following reduction language packages the preceding coefficient conditions in a form closer to classical collapse theory.

6.3 Free-acyclic reducibility↩︎

The previous characterization is equivalent to perfectness. We now isolate a more restrictive, easily checkable sufficient certificate lying strictly between collapsibility and perfectness.

6.4 Optimal critical-cell recursion↩︎

The same recursion also controls optimal, not necessarily perfect, Morse vectors. Define \[\mu(K)=\min\left\{\sum_i a_i: [z_0^{a_0}\cdots z_d^{a_d}]\mathcal{ME}_K\neq0\right\},\] the minimum total number of critical cells among all acyclic matchings on \(K\). For a polynomial \(P\) with non-negative coefficients, let \[\nu(P)=\min\left\{\sum_i a_i:[z^a]P\neq0\right\}, \qquad \nu(0)=\infty.\]

7 The Independence ME Polynomial \(\Phi(G)\) as a Graph Invariant↩︎

7.1 The invariant \(\Phi(G)\)↩︎

The previous sections establish the Laplacian Formula and its applications. We now prove the third main result, a graph invariant which strictly refines the graph-level Morse ensemble \(\mathcal{ME}_G\) and distinguishes examples not separated by \(T_G\) or \(I(G;t)\). The idea is to apply the ME polynomial to a higher-dimensional simplicial complex canonically associated to a graph, its independence complex.

The invariant \(\Phi(G)\) can be understood as follows. While \(\mathcal{ME}_G\) encodes the discrete Morse structure on the vertex-edge incidence of \(G\) (a \(1\)-dimensional problem), \(\Phi(G)\) encodes the full Morse ensemble on the independence complex \(\mathop{\mathrm{Ind}}(G)\), a higher-dimensional complex whose topology reflects the independence structure of \(G\). Specifically:

• \(I(G;t)=f(\mathop{\mathrm{Ind}}(G);t)\) reads only the \(f\)-vector of \(\mathop{\mathrm{Ind}}(G)\) (how many simplices in each dimension), while \(\Phi(G)\) reads the full Morse structure—how many critical simplices of each dimension can arise in any acyclic matching.

• \(T_G\) reads only the cycle matroid (which subsets of edges are forests), while \(\Phi(G)\) encodes the homotopy and combinatorial topology of \(\mathop{\mathrm{Ind}}(G)\), which reflects the global independence structure of \(G\) beyond forests.

The equalities \(T_{G_1}=T_{G_2}\) and \(I(G_1;t)=I(G_2;t)\) encode only the cycle matroid structure and the \(f\)-vector of \(\mathop{\mathrm{Ind}}(G_i)\), respectively. Neither captures the fine combinatorial structure of \(\mathop{\mathrm{Ind}}(G_i)\) required to separate these complexes. The remarkable aspect of Theorem 32 is not merely that \(\Phi(G)\) separates more graphs than \(T_G\) or \(I(G;t)\), but that it does so even when the separated complexes share homotopy type. The ME polynomial of the independence complex is therefore a genuinely combinatorial invariant, sensitive to information beyond homotopy type, f-vector, and cycle matroid.

By the Collapsibility Criterion (Proposition 21), \([z_0]\Phi(G)\) counts collapsing matchings of \(\mathop{\mathrm{Ind}}(G)\); in particular, it is positive precisely when \(\mathop{\mathrm{Ind}}(G)\) is collapsible. This is not the main reason for introducing \(\Phi\), but it explains the witness in Theorem 32: both independence complexes are collapsible, yet the collapse counts differ, \[[z_0]\Phi(G_1)=270,\qquad [z_0]\Phi(G_2)=324.\] Thus \(\Phi\) records collapse-level combinatorial information invisible to \(T_G\), \(I(G;t)\), and homotopy type.

7.2 Independence of \(\Phi\) from Laplacian invariants↩︎

The pair of graphs in Theorem 32 satisfies \(T_{G_1}=T_{G_2}\) but does not have \(\mathcal{ME}_{G_1}=\mathcal{ME}_{G_2}\) (the Laplacian spectra differ). We next show that even the graph-level Morse ensemble polynomial \(\mathcal{ME}_G\) does not determine \(\Phi(G)\).

We next prove the converse structural statement: although \(\mathcal{ME}_G\) does not determine \(\Phi(G)\), the independence \(\mathcal{ME}\) polynomial \(\Phi(G)\) does determine the graph-level Morse ensemble polynomial \(\mathcal{ME}_G\).

Combining Theorem 33 with Theorem 34, we obtain the strict hierarchy \[\Phi(G) \quad\Longrightarrow\quad \mathcal{ME}_G, \qquad \mathcal{ME}_G \not\Longrightarrow \Phi(G).\] Thus the independence ME polynomial is a strict refinement of the one-dimensional graph Morse ensemble invariant, rather than an independent invariant in the opposite direction.

8 Open problems↩︎

Open problems.

1. Recovery from \(\Phi(G)\). Theorem 34 shows that \(\Phi(G)\) determines \(\mathcal{ME}_G\), and hence the Laplacian spectrum of \(G\). Which further graph parameters are functions of \(\Phi(G)\)? For instance, is the chromatic polynomial \(\chi(G;t)\) always recoverable from \(\Phi(G)\)? Does \(\Phi(G)\) separate non-isomorphic graphs in restricted classes (e.g.forests, bipartite graphs, or planar graphs)?

2. Combinatorial formula for the collapsing-matching count. For collapsible independence complexes, is there a closed formula for \([z_0]\Phi(G)\) analogous to \([z_0 z_1^{m-n+1}]\mathcal{ME}_G = n\tau(G)\)? The value \([z_0]\Phi(P_4)=4\) is suggestive but the general pattern is not yet clear.

3. Perfect Morse counts in higher dimensions. For graphs, \([z_0 z_1^{\beta_1}]\mathcal{ME}_G = n\tau(G)\) via the Matrix-Tree theorem (Theorem 13). In dimension two, \([z_0z_2]\mathcal{ME}_{\partial\Delta^3}=256=4\cdot4\cdot\tau(K_4)\). Duval–Klivans–Martin’s simplicial Matrix-Tree theorem [22] provides the natural candidate tool for a general formula, but the correct generalisation likely involves compatible families of weighted cellular spanning trees rather than a single top-dimensional tree enumerator.

4. Computational complexity. The Laplacian Formula computes \(\mathcal{ME}_G\) in polynomial time. For higher-dimensional complexes, computing \(\mathcal{ME}_K\) exactly is conjectured \(\#P\)-hard by analogy with Tutte polynomial evaluation, but a precise reduction is open.

5. Closed forms for the non-liftable correction. The correction \(F(K,\sigma,\tau)\) is controlled by incidence geometry: Theorem 17 gives the exact vanishing criterion, and Theorem 18 gives the leading obstruction layer. Can the path-forced inclusion–exclusion formula of Remark 19 be converted into effective closed forms for broad classes of complexes, for instance incidence forests, manifold-like pseudomanifolds, or the one-dimensional non-bridge case?

References↩︎