Algebra combinatoria

algebra combinatoria

algebra combinatoria o combinatoria algebrica, settore di studi che utilizza metodi combinatori, cioè di ordinamento e conteggio, per lo studio di problemi algebrici o, viceversa, utilizza metodi algebrici in diversi contesti combinatoriali. Si utilizzano per esempio metodi combinatori nello studio delle → azioni di un gruppo su un insieme parzialmente ordinato, nell’analisi delle → rappresentazioni di strutture algebriche su spazi vettoriali, nell’analisi dei grafi parziali estratti da → grafi (che si generalizzano in modo naturale alle → matroidi). Viceversa, strutture algebriche, tipicamente i gruppi, sono impiegate per analizzare gli isomorfismi o gli automorfismi di reticoli o grafi e più in generale forme di rappresentazione particolarmente importanti per le applicazioni in informatica e in teoria degli algoritmi (si pensi per esempio alle diverse procedure di visita di un albero binario).

Anche se alcuni autori, in un passato anche recente, hanno teso a definire i problemi dell’algebra e dell’analisi combinatoria come semplici rompicapo, con scarso riferimento alla matematica pura e concettuale, in realtà, lo stesso Eulero mosse il primo approccio verso la topologia proprio a partire da un problema d’ordine pratico che ha a che vedere con grafi e percorsi: il problema dei ponti di → Königsberg. Verso la fine del xix secolo A. Cayley pubblicò un articolo nel quale riproponeva il problema sollevato da F. Guthrie, sul numero minimo di colori da usare nelle carte geografiche, il cosiddetto problema dei → quattro colori, che ha visto la completa soluzione solo nella seconda metà del secolo successivo grazie all’impiego di potenti calcolatori (per opera di K. Appel e W. Haken nel 1976). Nel corso del xx secolo l’algebra combinatoria cominciò a trovare un proprio posto nella matematica tradizionale, attraverso lo studio da parte di G.H. Hardy e J.E. Littlewood del comportamento asintotico del numero p(n) di modi in cui scrivere il numero n come somma di interi positivi (senza tenere conto dell’ordine). Questi e altri studi hanno mostrato il legame tra problemi di conteggio di oggetti e analisi matematica, attraverso l’impiego di serie formali di potenze, i coefficienti delle quali sono appunto i numeri che contano gli oggetti in considerazione.

Sono inoltre molto stretti i legami tra algebra combinatoria e informatica. I computer, infatti, danno la possibilità di compiere lunghe analisi di tutte le possibili configurazioni di un problema in tempi non comparabili con quelli della capacità umana e permettono così di seguire procedure di esaustione dei casi possibili, altrimenti non ipotizzabili. Queste «prove» per esame di tutte le configurazioni possibili hanno aperto un dibattito tra matematici circa la loro caratterizzazione teorica, se cioè sia possibile accettare come dimostrazione un procedimento non controllabile dall’uomo.

Nella direzione opposta, anche l’informatica teorica è stata foriera di nuovi problemi per l’algebra combinatoria. Per esempio, J. Paris e L. Harrington hanno formulato un enunciato di carattere matematico non dimostrabile nell’aritmetica di Peano, stabilendo che tale enunciato non è dimostrabile a partire dagli assiomi in quanto la corrispondente funzione che ne realizzerebbe la dimostrazione cresce più rapidamente di ogni funzione calcolabile. È un risultato non dissimile da quello a cui era giunto K. Gödel nel 1931, in un’epoca ben lontana dall’avvento dei moderni computer (→ Gödel, teorema di), ma mentre l’enunciato non dimostrabile formulato da Gödel non aveva significato matematico diretto, quello formulato da Paris e Harrington lo ha.