Hamilton decompositions of all directed tori at odd modulus

Sintesi Tecnica: Un Teorema di Chiusura per il Conto dei Prefissi sulle Decomposizioni Hamiltoniane dei Tori Diretti a Moduli Pari

Enunciato del Problema
Il lavoro affronta il problema della decomposizione Hamiltoniana per i prodotti cartesiani diretti di cicli, in particolare il toro $d$-dimensionale orientato a lati uguali $D_d(m) = \text{Cay}((\mathbb{Z}/m\mathbb{Z})^d, \{e_0, \dots, e_{d-1}\})$. Una decomposizione Hamiltoniana richiede di partizionare gli $d|V|$ archi del grafo in esattamente $d$ cicli Hamiltoniani diretti disgiunti. Sebbene l'Hamiltonicità (l'esistenza di un singolo ciclo ricoprente) per tali grafi sia ampiamente studiata, il più forte problema di partizione degli archi per tutte le dimensioni $d \ge 2$ e moduli dispari $m \ge 3$ rimaneva irrisolto. Il lavoro mira a dimostrare che $D_d(m)$ ammette una decomposizione Hamiltoniana diretta per ogni intero $d \ge 2$ e ogni intero dispari $m \ge 3$.

Metodologia
La strategia di dimostrazione si basa su due meccanismi di chiusura primari che consentono la costruzione di decomposizioni per dimensioni arbitrarie partendo da un insieme di dimensioni "risolte" di base. La metodologia è divisa in due rami in base alla relazione tra il modulo $m$ e la dimensione $d$:

1. Ramo del Conto ad Alto Modulo ($m \ge d$):

   • Certificati Piani-Radice: Gli autori introducono un "certificato piano-radice", una struttura definita sulla somma dei livelli $S(x) = \sum x_i = 0$. Ciò riduce il problema globale di decomposizione alla costruzione di mappe locali su una fetta piano-radice $A_{d,m}$.
   • Coordinate dei Prefissi e Fattorizzazione a Singolo Livello: Lo spazio piano-radice è mappato in coordinate dei prefissi tramite una biiezione triangolare. La decomposizione è costruita livello per livello utilizzando mappe $M^\sigma_c$ che permutano le coordinate dei prefissi in base a insiemi di simboli $\{0, \Delta, 2, \dots, d-1\}$.
   • Primitività del Conto dei Prefissi: Un criterio chiave (Teorema 4.4) garantisce che la composizione di queste mappe a livelli formi un singolo ciclo. Ciò richiede condizioni specifiche sul conteggio dei simboli utilizzati nella sequenza: $\gcd(N_0, m) = 1$ e $\gcd(N_k - N_\Delta, m) = 1$ per $k \ge 2$.
   • Livelli Binari con Segno: Per soddisfare queste condizioni di conteggio per $m \ge d$ (dove $d$ è dispari), gli autori costruiscono "matrici di conteggio ammissibili per i prefissi". Per $q \ge 2$ (dove $m = (d-1)q + r$), essi utilizzano livelli binari con segno (matrici con voci $\{-2, -1, 1, 2\}$) per bilanciare le somme di righe e colonne mantenendo le unità modulari richieste. Un'adeguata correzione di accoppiamento gestisce il caso limitato $q=1$.

2. Ramo del Commercio Modulare Base-Coda ($m < d$):

   • Sollevamento Base-Coda: Quando il modulo è piccolo rispetto alla dimensione, il lavoro impiega una costruzione "base-coda". Una dimensione di base risolta $b$ (dove $D_b(m)$ è decomponibile) è combinata con una coda di dimensione $T = d-b$.
   • Decomposizione in Cilindri: Il multigrafo di base è decomposto in cilindri. Gli archi attivi nella base sono assegnati a simboli da un alfabeto di coda per programmare "scambi locali di simboli".
   • Programmazione del Residuo Attivo: Utilizzando un "serbatoio di scambio cilindrico", gli autori riservano vertici specifici per eseguire scambi locali di simboli tra colori. Ciò consente di aggiustare i residui di conteggio colore-simbolo per soddisfare le condizioni di primitività del conto dei prefissi richieste per la dimensione della coda, sollevando efficacemente la decomposizione di base alla dimensione completa $d$.

Contributi Chiave

• Due Meccanismi di Chiusura: Il lavoro stabilisce due regole di chiusura distinte per l'insieme $S$ delle dimensioni risolte:
  • Chiusura per Prodotto: Se $a, b \in S$, allora $ab \in S$.
  • Chiusura per Successore: Se $b \in S$ e $b \ge 5$, allora $2b + 1 \in S$.
• Costruzione ad Alto Modulo: Una costruzione uniforme per $d \ge 5$ dispari e $m \ge d$ che utilizza livelli binari con segno e matrici di conteggio dei prefissi, indipendente da qualsiasi dimensione di base pre-risolta.
• Teorema del Commercio Modulare Base-Coda: Un teorema generale (Teorema 1.3) che risolve $D_d(m)$ per $m < d$ data una base risolta $b$, purché $d$ possa essere decomposto in somme di unità modulo $m$ e siano soddisfatte specifiche disuguaglianze dimensionali ($T > b$ e $mb > m \cdot d \cdot T$).
• Formalizzazione: I risultati sono accompagnati da una formalizzazione in Lean (Lean 4) che verifica il teorema per tutte le dimensioni e la specifica struttura di dipendenza della dimostrazione.

Risultati
Il lavoro dimostra il Teorema 1.5: Per ogni intero $d \ge 2$ e ogni intero dispari $m \ge 3$, il toro Cayley diretto di base $D_d(m)$ ammette una decomposizione Hamiltoniana diretta.

La dimostrazione procede identificando un insieme minimo di dimensioni di base:

• Dimensioni 2 e 3: Dimostrato nell'Appendice B (la Dimensione 2 è classica; la Dimensione 3 è dimostrata per $m$ dispari).
• Dimensioni 5 e 7: Tratte da teoremi esterni citati ([22], [23]).

Utilizzando le regole di chiusura:

• La chiusura per prodotto genera le dimensioni $4, 6, 8, 9, 10, \dots$.
• La chiusura per successore (iniziando da $b=5$) genera $11$, e successivamente dimensioni dispari superiori.
• Un argomento di "intercettazione di intervalli diadici-triadici" (Lemma 10.3) mostra che per ogni $d \ge 29$ dispari, esiste una base risolta $b \in \langle 2, 3 \rangle$ tale che le condizioni base-coda sono soddisfatte.
• L'induzione forte conferma che ogni $d \ge 2$ è coperto.

Significato e Affermazioni
Il lavoro afferma di risolvere il problema della decomposizione Hamiltoniana per l'intera classe dei tori diretti a lati uguali con moduli dispari. Posiziona questo lavoro come soluzione al problema della partizione degli archi, che è più forte del problema dell'Hamiltonicità affrontato nella letteratura precedente (ad esempio, Trotter–Erdős, Curran–Witte).

Gli autori sottolineano la natura strutturale della dimostrazione:

• Unifica i casi ad alto modulo e basso modulo attraverso meccanismi distinti ma complementari (matrici di conteggio vs. scambi modulari).
• Riduce il problema infinito di tutte le dimensioni a un insieme finito di input di base (2, 3, 5, 7) e due operazioni algebriche di chiusura.
• L'inclusione di una formalizzazione verificabile da macchina funge da artefatto di verifica per gli argomenti combinatori complessi, in particolare le intricate condizioni di conteggio e accoppiamento nel ramo base-coda.

Il lavoro non afferma di risolvere il problema per moduli pari o tori non a lati uguali, né propone nuove applicazioni oltre alla risoluzione teorica di questo specifico problema di decomposizione. Il significato risiede nella completezza del risultato per la classe specificata di grafi e nella rigorosa verifica formale fornita.