Anupam Mondal ; Sajal Mukherjee ; Kuldeep Saha - Topology of matching complexes of complete graphs via discrete Morse theory

dmtcs:12887 - Discrete Mathematics & Theoretical Computer Science, November 4, 2024, vol. 26:3 - https://doi.org/10.46298/dmtcs.12887
Topology of matching complexes of complete graphs via discrete Morse theoryArticle

Authors: Anupam Mondal ORCID; Sajal Mukherjee ORCID; Kuldeep Saha ORCID

    Bouc (1992) first studied the topological properties of Mn, the matching complex of the complete graph of order n, in connection with Brown complexes and Quillen complexes. Björner et al. (1994) showed that Mn is homotopically (νn1)-connected, where νn=n+131, and conjectured that this connectivity bound is sharp. Shareshian and Wachs (2007) settled the conjecture by inductively showing that the νn-dimensional homology group of Mn is nontrivial, with Bouc's calculation of H1(M7) serving as the pivotal base step. In general, the topology of Mn is not very well-understood, even for a small n. In the present article, we look into the topology of Mn, and M7 in particular, in the light of discrete Morse theory as developed by Forman (1998). We first construct a gradient vector field on Mn (for n5) that doesn't admit any critical simplices of dimension up to νn1, except one unavoidable 0-simplex, which also leads to the aforementioned (νn1)-connectedness of Mn in a purely combinatorial way. However, for an efficient homology computation by discrete Morse theoretic techniques, we are required to work with a gradient vector field that admits a low number of critical simplices, and also allows an efficient enumeration of gradient paths. An optimal gradient vector field is one with the least number of critical simplices, but the problem of finding an optimal gradient vector field, in general, is an NP-hard problem (even for 2-dimensional complexes). We improve the gradient vector field constructed on M7 in particular to a much more efficient (near-optimal) one, and then with the help of this improved gradient vector field, compute the homology groups of M7 in an efficient and algorithmic manner. We also augment this near-optimal gradient vector field to one that we conjecture to be optimal.


    Volume: vol. 26:3
    Section: Combinatorics
    Published on: November 4, 2024
    Accepted on: September 18, 2024
    Submitted on: January 18, 2024
    Keywords: Mathematics - Combinatorics,Mathematics - Algebraic Topology,Mathematics - Geometric Topology,57Q70 (primary), 05C70, 05E45

    Consultation statistics

    This page has been seen 462 times.
    This article's PDF has been downloaded 228 times.