Complexes of discrete Morse functions

DOI10.1016/J.DISC.2004.07.027MaRDI QIDQ2575785zbMATH OpenOpenAlexWikidataFDO

Publication date 6 December 2005

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0011234

Collapsibility Discrete Morse theory Matrix-Tree theorem

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) PL-topology (57Q99) Critical points and critical submanifolds in differential topology (57R70) Abstract critical point theory (Morse theory, Lyusternik-Shnirel'man theory, etc.) in infinite-dimensional spaces (58E05)

Abstract: We investigate properties of the set of discrete Morse functions on a simplicial complex as defined by Forman. It is not difficult to see that the pairings of discrete Morse functions of a finite simplicial complex again form a simplicial complex, the discrete Morse complex. It turns out that several known results from combinatorial topology and enumerative combinatorics, which previously seemed to be unrelated, can be re-interpreted in the setting of these discrete Morse complexes.

Review text

The authors define the simplicial complex \(M(\Delta)\) of all \textit{discrete Morse functions} (in the sense of Forman's discrete Morse theory for cell complexes [\textit{R. Forman}, Adv. Math.134, No. 1, 90--145 (1998; Zbl 0896.57023)] of a fixed simplicial complex~\(\Delta\), and study the special cases where \(\Delta\)~is a graph, respectively a simplex. The main technical tool is the identification (due to Forman) of discrete Morse functions with \textit{acyclic matchings} (so-called \textit{Morse matchings}) in the directed Hasse diagram of~\(\Delta\). For \(\Delta=\Gamma\) a graph, the acyclic matchings of its Hasse diagram (and thus the discrete Morse functions) are just the rooted forests of~\(\Gamma\), studied before by \textit{D. N. Kozlov} [J. Combin. Theory Ser. A 88, No. 1, 112--122 (1999; Zbl 0934.05041)]. For general graphs~\(\Gamma\), the authors relate the \(f\)-vector \(f_*=(f_0, f_1,\dots)\) of \(M(\Gamma)\) to the characteristic polynomial \(\sigma(\Gamma,\mu)=\det(\mu I-Q(\Gamma))\) of the Laplacian~\(Q(\Gamma)\) via the formula \[ \sigma(\Gamma,\mu) \;= \;\sum_{i\geq0} f_{i-1} (-1)^i \mu^{n-i}, \] where \(n\)~denotes the number of vertices of~\(\Gamma\). In the special case where \(\Gamma=C_n\) is the \(n\)-cycle, the authors show that the homotopy type of the \textit{pure} Morse complex of~\(C_n\) -- i.e., the simplicial complex \(M_{\text{pure}}(C_n)\) induced by the facets of~\(M(C_n)\) -- is \(S^2\vee S^{n-2} \vee S^{n-2}\) for~\(n\geq4\). In the previously cited paper, Kozlov had calculated the homotopy type of the entire Morse complex~\(M(C_n)\) to be \[ M(C_n) \;\simeq\;\begin{cases} S^{2k-1} \vee S^{2k-1} \vee S^{3k-2} \vee S^{3k-2} & { \text{ if }} n=3k,\\ S^{2k} \vee S^{3k-1} \vee S^{3k-1} & \text{ if } n=3k+1,\\ S^{2k} \vee S^{3k} \vee S^{3k} & \text{ if } n=3k+2. \end{cases} \] In the case where \(\Delta=\Delta_d\) is the \(d\)-dimensional simplex, the authors obtain \(M(\Delta_1)\simeq S^0\) and \(M(\Delta_2)\simeq S^1\vee S^1\vee S^1 \vee S^1\). For \(d\geq3\), the Morse complex of~\(\Delta_d\) is no longer pure. The authors calculate the \(f\)-vector and reduced integer homology of \(M(\Delta_3)\) to be \[ f_*(M(\Delta_3)) = (28,300,1544,3932,4632,2128,256), \] \[ H_*(M(\Delta_3),{\mathbb Z}) = (0,0,0,0,{\mathbb Z}^{99},0,0); \] analogously, they obtain \[ f_*(M_{\text{pure}}(\Delta_3)) = (28,300,1544,3680,3672,1600,256), \] \[ H_*(M_{\text{pure}}(\Delta_3),{\mathbb Z}) = (0,0,0,{\mathbb Z}^{81},0,0,0). \] Finally, the facets of \(M_{\text{pure}}(\Delta)\) correspond to the \textit{perfect} Morse matchings in the Hasse diagram of~\(\Delta\). In the case \(\Delta=\Delta_d\), the authors obtain the asymptotic bounds \[ (1.289)^{2^d} \;\leq\;f(d) \;\leq \;(d+1)^{2^{d-1}} \] for the number \(f(d)\) of facets of \(M_{\text{pure}}(\Delta_d)\), using the notion of \textit{\((k,d)\)-trees} due to \textit{G. Kalai} [Isr. J. Math. 45, 337--351 (1983; Zbl 0535.57011)] for the upper bound, and for the lower bound the interpretation of Morse matchings of~\(\Delta_d\) as special types of perfect matchings in the graph of the \((d+1)\)-dimensional cube.

Recommendations

Cites work

Cited in

(31)

Describes a project that uses

Uses Software

This page was built for publication: Complexes of discrete Morse functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2575785)