Discrete Morse theory simplifies a cell complex, meaning a space glued together from points, edges, triangles and higher cells, by pairing cells and cancelling each pair. The cells left unpaired, called critical cells, form a smaller complex with the same homotopy type. This collapsing technique sits behind the proof of the $K(\pi,1)$ conjecture for affine Artin groups by Paolini and Salvetti and behind the homology computations of weighted sheaves over posets. The conjecture says that certain hyperplane complements are classifying spaces, with all of their topology carried by the fundamental group. Finding a matching with the fewest critical cells is a combinatorial optimization problem. Proving that a given matching is optimal is harder still. The best exact method, branch-and-cut over an integer program, solves some benchmark complexes in seconds. It ran for over a week on a 1,112-variable triangulation of the Poincaré homology sphere without finishing, because the lower bounds that homology supplies, the number of critical $k$-cells being at least the $k$-th Betti number, were not tight there.
This note proposes to explain that failure with a theorem rather than an anecdote. Our claim is that short linear-inequality certificates of Morse optimality exist when the obstruction to collapsing is visible to homology, including torsion, and provably do not exist when the obstruction is homologically invisible. Torsion here means elements of finite order in the homology groups, which the integer boundary matrices detect and rational homology misses. The lower-bound half comes from composing two existing results. The first is the reduction of Bauer and Rathod, which encodes monotone circuit satisfiability into 2-complexes using "dunce hat" gadgets: spaces that are contractible yet cannot be collapsed. The second is the query-to-communication lifting theorem of Garg, Göös, Kamath and Sokolov, which turns formulas that are hard for Resolution into formulas that are hard for Cutting Planes. Cutting Planes is the proof system that underlies cutting-plane integer programming; a refutation in it derives a contradiction by repeatedly combining linear inequalities and rounding.
Core Claim
We conjecture a dichotomy for the integer program "this complex admits an acyclic matching with at most $c$ critical cells." The program has 0/1 variables $x_{\sigma\tau}$, one for each pair of a cell $\sigma$ and a facet $\tau$ of it. Its constraints are the matching constraints and the cycle inequalities of Joswig and Pfetsch, and we optionally add homological axioms. These axioms are the Betti inequalities $c_k \ge \beta_k$, where $c_k$ counts critical $k$-cells and $\beta_k$ is the $k$-th Betti number. We also add their torsion-aware strengthening, $c_k \ge \beta_k + t_k + t_{k-1}$, where $t_k$ is the minimal number of generators of the torsion part of $H_k$.
The upper-bound side of the dichotomy concerns complexes where some matching meets these homological bounds exactly. For those complexes, Cutting Planes using the homological axioms should certify optimality in polynomial size. The lower-bound side concerns a family of 2-complexes with trivial integral homology, so that every homological axiom is essentially vacuous. For that family, any Cutting Planes refutation of "$c \le c^\ast - 1$" needs size $2^{n^{\Omega(1)}}$, where $c^\ast$ is the true optimum.
The structural reason for the upper bound is worth stating plainly. The Hasse diagram of a complex is the graph linking each cell to its facets. It is bipartite between adjacent dimensions, so the plain matching polytope is integral, because its constraint matrix is totally unimodular. A matrix is totally unimodular when every square submatrix has determinant $-1$, $0$ or $1$. This is the same property that Lafont, Ortiz, Rahm and Sánchez-García use, applied to boundary blocks, to certify that homology is torsion-free. The acyclicity requirement is what destroys integrality. Our thesis is that the integrality gap introduced by acyclicity can be closed by homological reasoning exactly when homology sees the obstruction.
Research Program
The central technical step is showing that the Bauer–Rathod reduction is local. Each matching variable $x_{\sigma\tau}$ in the target complex should be computable by a constant-depth decision tree over the variables of the source monotone circuit. Locality is what lets a short Cutting Planes refutation for the complex be pulled back into a short refutation for the source formula, with only polynomial overhead.
Bauer and Rathod built their gadgets to preserve approximation ratios, which is a weaker requirement. We will either verify locality for their construction or redesign the dunce-hat gadgets so that each gadget's internal matching is forced by a bounded number of circuit wires. Their $W[P]$-hardness, parameterized by the number of critical cells, suggests the wire structure is already confined in this way, but this is unproven.
Given locality, we take a CNF formula that is hard for Resolution. We lift it with the index gadget of Garg et al. to get a formula hard for Cutting Planes. We translate that formula into a monotone-circuit instance, and finally into a 2-complex whose minimum Morse matching problem inherits the lower bound. We then check that adding the homological axioms does not help. The gadget complexes are built from contractible pieces, so these axioms reduce to inequalities like $c_0 \ge 1$, which the lifted hardness easily absorbs.
The upper-bound side targets complexes certified by algebra. We will check it on finite complexes from the Artin-group literature, namely Salvetti complexes of spherical types and the finite dual models constructed by Paolini and Salvetti. On these complexes, precise matchings in the sense of the weighted-sheaf paper reduce homology to ranks of incidence matrices. We aim to prove that if some matching attains the torsion-aware bounds, a polynomial-size Cutting Planes derivation from the homological axioms certifies it. The derivation would sum per-dimension rank arguments.
This side also explains where torsion matters. On a complex with $\mathbb{Z}/p$ torsion, the plain Betti axioms are too weak and the torsion-aware axioms close the gap. Integer boundary matrices that fail total unimodularity are the signature of this regime.
The two sides play different roles in the program. Lifting supplies the hardness, Artin-group complexes supply the structured "easy" regime, and torsion marks the boundary between them.
Baselines
The naive reference point is the Morse-matching integer program solved by plain branch-and-bound without cycle separation. Joswig and Pfetsch report that this took over 16 million nodes and 19,359 seconds on c-ns.
The strongest existing exact method is their branch-and-cut with cycle-inequality separation plus Betti cuts. They report solving c-ns in 1.95 seconds with 28 nodes. They also report that poincare (1,112 variables) "could not be solved even after running for a week." We will reimplement it with the same solver, the same separation routines, the same per-instance time cap and the same hardware for every instance family. Beating this baseline does not mean solving faster. It means predicting its scaling. On lifted gadget complexes its node count should grow exponentially in the source formula size $n$. On algebraically certified complexes of matched size it should stay polynomial.
The strongest heuristic is the $O(n/\log n)$ erasing-gradient approximation of Bauer and Rathod. It serves as a primal bound, so that we can report the gap between heuristic matchings and certified lower bounds. We found no reported empirical result on Lacuna for this algorithm on any benchmark.
Two ablations isolate the key ingredients. The first replaces the index gadget with a trivial gadget of the same cell count. If hardness disappears, it was caused by lifting and not by complex size. The second toggles the torsion-aware cuts on and off. This should matter only on complexes with torsion.
Why not just…?
Why not just cite NP-hardness of minimum Morse matching? Bauer and Rathod prove NP-hardness and strong inapproximability. These results are conditional on P ≠ NP and say nothing about which instances defeat a particular solver. They also cannot explain why Betti-bounded complexes are easy. An exponential Cutting Planes lower bound holds unconditionally against every pure cutting-plane procedure, and the dichotomy names the instances. One limitation must be stated honestly: branch-and-cut, which branches on variables as well as cutting, is stronger than Cutting Planes. Our lower bound covers it only empirically, through the node-count experiments.
Why not just add stronger topological cuts? This is the real threat. Torsion-aware cuts are vacuous on contractible gadgets, and the torsion ablation will show that directly. However, cuts derived from the fundamental group, or from local non-collapsibility, could see the dunce-hat obstruction and shortcut our bound. The bound is stated relative to a fixed axiom set. If a natural cut family breaks it on the generated instances, we will record that and refine the claim to "homotopically invisible" obstructions.
Why not just reduce a known Cutting-Planes-hard formula directly, without new lifting? That is essentially what we do. The hardness comes entirely from Garg et al., and we prove no new lifting theorem. The new content is the locality of the topological reduction and the matching upper bound. The trivial-gadget ablation confirms that the source hardness, and not the topology alone, drives the measured blow-up.
Proposed Experiments
We will run the reimplemented branch-and-cut on four instance families. The first is the Hachimori benchmark complexes used by Joswig and Pfetsch: dunce, rudin, ziegler, mani-walkup-C, c-ns, CP2, MNSS and poincare. The second is generated lifted Bauer–Rathod complexes, built from Resolution-hard pigeonhole and Tseitin formulas with $n$ ranging from 5 to 40. The third is size-matched controls built with the trivial gadget. The fourth is Salvetti complexes of spherical Artin types, together with Paolini–Salvetti finite dual models for small affine types.
For each instance we record branch-and-bound nodes, wall-clock time to a certified optimum, and the final integrality gap at a 24-hour cap. We fit growth curves of nodes against $n$ for each family.
The decisive check is a family-level separation. The lifted family should show exponential node growth while the controls and the Artin-group complexes stay polynomial at equal variable counts. Torsion-aware cuts should change outcomes only on instances with torsion. If the lifted family is solved quickly, then either the locality step fails or branching circumvents the Cutting Planes bound. Each of those outcomes is informative.