La congettura di Rota

Attenzione: i contenuti sono abbastanza avanzati, più del solito. Forse anche la semplificazione non è così... semplice. Ad ogni modo, spero ci proviate lo stesso a leggerlo tutto, o almeno solo un pochino!

---

Uno degli aspetti più interessanti dei matematici moderni, soprattutto di quelli di qualità, è la loro capacità di cogliere gli aspetti in comune tra branche apparentemente distanti tra loro. E' in effetti il caso della storia dietro la congettura scoperta nel 1970 da Gian-Carlo Rota⁽⁶⁾, che parte dalla definizione di matroide.
Questo oggetto dal nome forse non troppo rassicurante, introdotto nel 1935 da Hassler Whitney⁽³⁾ è, in effetti, una coppia di oggetti matematici, $(E, I)$, dove $E$ è in insieme finito, detto insieme ambiente, ed $I$ una collezione di sottoinsiemi di $E$ chiamati insiemi indipendenti, tale che

1. l'insieme vuoto è indipendente;
2. sottoinsiemi di insiemi indipendenti sono indipendenti;
3. per ogni insieme $X \subseteq E$, i maggiori sottoinsiemi indipendenti di $X$ hanno tutti la stessa dimensione.

Una matroide è, per esempio, una collezione di vettori in uno spazio vettoriale, o l'insieme delle colonne di una matrice. Data, quindi, una matrice, definita su un dato campo $F$ (l'insieme dei numeri che compongono le celle della matrice), si può costruire la matroide colonna della matrice di partenza costruendo i sottoinsiemi di colonne linearmente indipendenti della matrice stessa (l'insieme $I$ di una matrice $3 \times 3$ con colonne linearmente indipendenti sarà, quindi, costituito da 4 insiemi, quello formato dalle tre colonne prese insieme e i tre costituiti da ciascuna coppia di colonne).
Con un parallelo interessante con la teoria delle matrici e la topologia, si possono poi introdurre anche i concetti di base (il più grande insieme indipendente) e di rango (la grandezza di un massimo insieme indipendente) di un dato insieme $X$ in una matroide $M$. E visto che non siamo contenti, ecco il duale di una matroide $M$, indicato come $M^*$, che è esso stesso una matroide e che viene costruito utilizzando come basi i complementi delle basi di $M$.
Infine i minori di una matroide: siano $C$ e $D$ due insiemi di elementi di una matroide $M$. A partire da questi due insiemi si possono definire due nuove matroidi, una per sottrazione, $M \setminus D$, e una come contrazione, $M/C = (M^* \setminus C^*)$. Un minore di una matroide è, quindi, una matroide della forma $M \setminus D / C$.
Siamo quasi pronti per enunciare la congettura di Rota: ci manca solo da definire le matroidi $F$-rappresentabili. Una matroide assume questo ruolo se è la matroide colonna di una matrice definita sul campo $F$. La congettura scoperta da Rota è dunque:

Per ogni campo finito $F$, ci sono, a meno di un isomorfismo, solo un numero finito di minori esclusi per la classe di matroidi $F$-rappresentabili.⁽⁵⁾

dove per minori esclusi si intendono i matroidi che non appartengono alla classe dei minori propri, ovvero quei minori per cui l'intersezione tra gli insiemi $C$ e $D$ è non nulla.
La dimostrazione di questa congettura ha stimolato lo sviluppo della teoria dei matroidi e permesso di esplorare il suo legame con la teoria dei grafi, e quindi con un approccio più geometrico ai matroidi. Non a caso, infatti, i grafi di Kuratowski⁽¹⁾ (vedi il problema dei servizi) risultano una rappresentazione grafica di due minori esclusi:

Quelle che possiamo chiamare come matroidi grafiche furono già osservate dallo stesso Whitney⁽²⁾ e da Tuttle⁽⁴⁾: esse sono rappresentabili su ogni campo e permettono agilmente di passare a strutture differenti semplicemente eliminando delle righe. In queste operazioni, però, bisogna stare attenti, perché il nuovo grafo non è necessariamente una matroide rappresentabile. Una variazione sul grafo $K_{3, 3}$ di Kuratowski, la matroide di Pappo, non è più rappresentabile sui reali per la sottrazione della linea centrale.⁽⁶⁾

---

(1) Kuratowski, Casimir. "Sur le problème des courbes gauches en Topologie." Fundamenta Mathematicae 15.1 (1930): 271-283.
(2) Whitney H. (1931). Non-Separable and Planar Graphs., Proceedings of the National Academy of Sciences of the United States of America, 17 (2) 125-127. PMID: 16587624
(3) Whitney, Hassler (1935). On the Abstract Properties of Linear Dependence American Journal of Mathematics, 57 (3), 509-533 DOI: 10.2307/2371182
(4) Tutte, W. T. (1959). Matroids and graphs Transactions of the American Mathematical Society, 90 (3), 527-527 DOI: 10.1090/S0002-9947-1959-0101527-3
(5) Rota, Gian-Carlo. Combinatoral theory, old and new. Proc. Internat. Cong. Math. (Nice 1970), 229-233. Gauthier-Villars, Paris. (pdf)
(6) Jim Geelen, Bert Gerards, & Geoff Whittle (2014). Solving Rota's Conjecture Notices of the American Mathematical Society, 61 (07), 736-743 DOI: 10.1090/noti1139