×

Complexes of discrete Morse functions. (English) Zbl 1091.57025

The authors define the simplicial complex \(M(\Delta)\) of all discrete Morse functions (in the sense of Forman’s discrete Morse theory for cell complexes [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 acyclic matchings (so-called 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 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 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 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 \((k,d)\)-trees due to 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.

MSC:

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

Software:

Homology; polymake
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Babson, E.; Björner, A.; Linusson, S.; Shareshian, J.; Welker, V., Complexes of not \(i\)-connected graphs, Topology, 38, 2, 271-299 (1999) · Zbl 0936.57002
[2] Biggs, N., Algebraic graph theory (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0797.05032
[3] Chari, M. K., On discrete Morse functions and combinatorial decompositions, Discrete Math., 217, 1-3, 101-113 (2000) · Zbl 1008.52011
[4] Clark, L. H.; George, J. C.; Porter, T. D., On the number of 1-factors in the \(n\)-cube, Congr. Numerantium, 127, 67-69 (1997) · Zbl 0901.05056
[5] J.-G. Dumas, F. Heckenbach, D. Saunders, V. Welker, Computing simplicial homology based on efficient smith normal form algorithms, in: M. Joswig, N. Takayma (Eds.), Algebra, geometry, and software systems, Springer, New York, 2003, pp. 177-206; J.-G. Dumas, F. Heckenbach, D. Saunders, V. Welker, Computing simplicial homology based on efficient smith normal form algorithms, in: M. Joswig, N. Takayma (Eds.), Algebra, geometry, and software systems, Springer, New York, 2003, pp. 177-206 · Zbl 1026.55010
[6] Forman, R., Morse theory for cell complexes, Adv. Math., 134, 1, 90-145 (1998) · Zbl 0896.57023
[7] E. Gawrilow, M. Joswig, TOPAZ module for polymake, version 2.0, with contributions by Thilo Schröder and Nikolaus Witte, free software, http://www.math.tu-berlin.de/polymake, 2003.; E. Gawrilow, M. Joswig, TOPAZ module for polymake, version 2.0, with contributions by Thilo Schröder and Nikolaus Witte, free software, http://www.math.tu-berlin.de/polymake, 2003.
[8] Graham, N.; Harary, F., The number of perfect matchings in a hypercube, Appl. Math. Lett., 1, 45-48 (1988) · Zbl 0626.05043
[9] F. Heckenbach, homology 3.0, http://www.mi.uni-erlangen.de/ heckenb/, 1999.; F. Heckenbach, homology 3.0, http://www.mi.uni-erlangen.de/ heckenb/, 1999.
[10] Jonsson, J., On the topology of simplicial complexes related to 3-connected and hamiltonian graphs, J. Combin. Theory Ser. A, 104, 1, 169-199 (2003) · Zbl 1031.05080
[11] Kalai, G., Enumeration of \(Q\)-acyclic simplicial complexes, Israel J. Math., 45, 337-351 (1983) · Zbl 0535.57011
[12] Kozlov, D. N., Complexes of directed trees, J. Comb. Theory Ser. A, 88, 1, 112-122 (1999) · Zbl 0934.05041
[13] J.W. Milnor, Morse theory. Based on lecture notes by M. Spivak and R. Wells, Annals of Mathematics Studies, vol. 51, Princeton University Press, Princeton, 1963.; J.W. Milnor, Morse theory. Based on lecture notes by M. Spivak and R. Wells, Annals of Mathematics Studies, vol. 51, Princeton University Press, Princeton, 1963.
[14] J. Palis, Jr, W. de Melo, Geometric theory of dynamical systems. An introduction, Translated from the Portuguese by A.K. Manning, Springer, New York, 1982, MR 84a:58004.; J. Palis, Jr, W. de Melo, Geometric theory of dynamical systems. An introduction, Translated from the Portuguese by A.K. Manning, Springer, New York, 1982, MR 84a:58004.
[15] Shareshian, J., Discrete morse theory for the complex of 2-connected graphs, Topology, 40, 4, 681-701 (2001) · Zbl 0980.57005
[16] R.P. Stanley, Enumerative combinatorics, vol. I, Wadsworth/Cole, Belmont, 1986.; R.P. Stanley, Enumerative combinatorics, vol. I, Wadsworth/Cole, Belmont, 1986. · Zbl 0608.05001
[17] Welker, V.; Ziegler, G. M.; Živaljević, R. T., Homotopy colimits—comparison lemmas for combinatorial applications, J. Reine Angew. Math., 509, 117-149 (1999) · Zbl 0995.55004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.