Cancellation of a critical pair in discrete Morse theory and its effect on (co)boundary operators

1. Problema e Contesto

La Teoria di Morse Discreta (introdotta da Forman) è uno strumento fondamentale per calcolare in modo efficiente i gruppi di omologia di complessi simpliciali. Il metodo si basa sull'assegnazione di un campo vettoriale gradiente discreto, che riduce il numero di simplessi necessari per il calcolo dell'omologia, identificando solo i "simplessi critici".

Il calcolo dell'omologia di Morse richiede l'enumerazione delle traiettorie gradiente (gradient trajectories) tra i simplessi critici per costruire gli operatori di bordo del complesso di Morse.
Un problema centrale è l'ottimizzazione di questo campo vettoriale: trovare un campo che minimizzi il numero di simplessi critici è un problema NP-hard. Una tecnica comune per migliorare un campo vettoriale esistente è la cancellazione di una coppia critica (due simplessi critici adiacenti collegati da un'unica traiettoria).

Tuttavia, la cancellazione di una coppia critica perturba l'insieme delle traiettorie gradiente. Di conseguenza, per calcolare l'omologia rispetto al nuovo campo vettoriale migliorato, è necessario rilevare e enumerare tutte le nuove traiettorie, un processo che può essere computazionalmente costoso e complesso.
Il paper affronta la domanda: Come possiamo aggiornare gli operatori di bordo (e di cobordo) dopo una cancellazione senza dover ricalcolare esplicitamente tutte le nuove traiettorie?

2. Metodologia

Gli autori adottano un approccio puramente combinatorio per derivare una formula esplicita che lega gli operatori di bordo del complesso di Morse prima e dopo la cancellazione di una coppia critica.

• Setup: Sia $\Delta$ un complesso simpliciale e $V$ un campo vettoriale gradiente. Sia $(\sigma_0^{(k)}, \tau_0^{(k-1)})$ una coppia critica cancellabile (esiste un'unica traiettoria $P_0$ da $\sigma_0$ a $\tau_0$).
• Cancellazione: Si costruisce un nuovo campo vettoriale $W$ invertendo le frecce lungo l'unica traiettoria $P_0$, rendendo $\sigma_0$ e $\tau_0$ non critici.
• Analisi delle Traiettorie: Gli autori analizzano la relazione tra le traiettorie $V$ (pre-cancellazione) e $W$ (post-cancellazione). Dimostrano che:
  1. Le traiettorie che non toccano la coppia cancellata rimangono invariate.
  2. Le nuove traiettorie in $W$ possono essere mappate biunivocamente a combinazioni di traiettorie in $V$ che coinvolgono la coppia cancellata.
• Derivazione Algebrica: Utilizzando i pesi delle traiettorie (definiti come prodotti di numeri di incidenza), gli autori dimostrano che il coefficiente di un semplice critico nell'operatore di bordo modificato può essere calcolato direttamente dai coefficienti originali tramite una sottrazione di termini specifici legati alla traiettoria cancellata.

3. Contributi Chiave e Risultati Principali

Il risultato principale è il Teorema 1.1, che fornisce una formula esplicita per l'operatore di bordo modificato $\partial^W$ in termini dell'operatore originale $\partial^V$.

Siano:

• $\sigma_0, \dots, \sigma_n$ i simplessi critici di dimensione $k$ in $V$ (dove $\sigma_0$ è quello cancellato).
• $\tau_0, \dots, \tau_m$ i simplessi critici di dimensione $k-1$ in $V$ (dove $\tau_0$ è quello cancellato).
• $a_{ij}$ i coefficienti dell'operatore $\partial^V_k$, tali che $\partial^V_k(\sigma_j) = \sum_{i=0}^m a_{ij} \tau_i$.

Dopo la cancellazione di $(\sigma_0, \tau_0)$, il nuovo operatore $\partial^W_k$ agisce sui rimanenti simplessi critici $\sigma_1, \dots, \sigma_n$ e $\tau_1, \dots, \tau_m$ secondo la formula:

$$\partial^W_k(\sigma_j) = \sum_{i=1}^m (a_{ij} - a_{00} a_{0j} a_{i0}) \cdot \tau_i \quad \text{per } j \in \{1, \dots, n\}$$

Interpretazione Matriciale:
La formula implica che la matrice rappresentativa di $\partial^W_k$ può essere ottenuta dalla matrice di $\partial^V_k$ (rimuovendo la riga 0 e la colonna 0) applicando una sequenza di operazioni elementari sulle righe (o colonne):

1. Si normalizza la riga 0 (poiché $a_{00} = \pm 1$).
2. Si sottrae dalla riga $i$ (per ogni $i \ge 1$) il prodotto $a_{i0} \cdot a_{00} \cdot (\text{riga } 0)$.
3. Si eliminano la riga 0 e la colonna 0.

Risultati Correlati:

• Operatori di Bordo Adiacenti: Per $q > k+1$ o $q < k-1$, gli operatori non cambiano ($\partial^W_q = \partial^V_q$). Per $q = k+1$, il termine relativo a $\sigma_0$ viene semplicemente rimosso. Per $q = k-1$, l'operatore è la restrizione di quello originale al sottogruppo dei simplessi rimanenti.
• Estensione al Cobordo: Il Teorema 3.6 estende questi risultati agli operatori di cobordo ($\delta$) del complesso co-Morse, mostrando che la matrice del cobordo modificato è la trasposta della matrice del bordo modificato, seguendo la stessa logica di operazioni elementari.

4. Significato e Implicazioni

1. Eliminazione della Ricalcolazione delle Traiettorie: Il contributo più significativo è l'eliminazione della necessità di enumerare le nuove traiettorie gradiente dopo una cancellazione. Invece di un processo combinatorio complesso, il problema si riduce a operazioni matriciali lineari (aggiunte e sottrazioni di righe/colonne) sui dati già calcolati.
2. Efficienza Computazionale: Questo approccio rende molto più efficiente l'aggiornamento dell'omologia di Morse quando si applicano algoritmi euristici o iterativi per ridurre il numero di simplessi critici (ad esempio, cancellazioni multiple).
3. Purezza Combinatoria: La dimostrazione è puramente combinatoria e non richiede l'uso di strumenti analitici pesanti, rendendo il risultato applicabile in contesti di topologia computazionale e analisi dei dati dove i complessi sono discreti e finiti.
4. Generalità: Il metodo si applica sia all'omologia che alla coomologia, fornendo un quadro completo per la manipolazione dei complessi di Morse.

In sintesi, il paper risolve un collo di bottiglia computazionale nella teoria di Morse discreta, trasformando un problema di ri-enumrazione di percorsi in un semplice problema di algebra lineare, facilitando così l'uso pratico della teoria per il calcolo dell'omologia su grandi dataset.