I grafi espansori

Il grafo è una nozione essenziale in matematica. Qui ci occuperemo di grafi formati da un numero finito di vertici, ciascuno collegato ad altri vertici da uno o più lati. Questi ultimi possono eventualmente essere orientati.

Un grafo può rappresentare, per esempio, una rete di comunicazione (come la rete tranviaria della città di Zürich o la rete della metropolitana parigina), la rete neurale di un animale (come il sistema nervoso del verme Caenorhabditis Elegans, l’unico animale di cui questa rete sia nota in modo esplicito e completo), oppure un albero genealogico (vedi les Graphes, Bibliothèque Tangente 54, 2015).

Per il tipo di questioni e di applicazioni che ci interessa maggiormente, i lati dei grafi considerati saranno supposti non orientati.

**

**

L’espansione nei grafi ======================================================================================================

Alcuni grafi particolari, detti espansori, possiedono proprietà così notevoli che la loro stessa esistenza sembra paradossale. In effetti, più di un matematico sembra aver dapprima pensato che non potessero esistere! Hanno inoltre applicazioni straordinarie in campi molto diversi della matematica e dell’informatica (combinatoria, geometria, aritmetica, teoria dei nodi…).

La storia dei grafi espansori è interamente moderna, poiché comincia alla fine degli anni Sessanta. Mostra in modo eclatante l’unità della matematica. Ancora oggi, in un’epoca in cui la ricerca è sempre più specializzata e spesso concettualmente difficile, possono emergere nuove idee rivoluzionarie, elementari e accessibili a un vasto pubblico.

Intuitivamente, un grafo espansore combina due proprietà che sembrano contraddittorie: da un lato, consente di muoversi molto efficacemente per collegare due vertici qualsiasi, anche se molti lati del grafo dovessero improvvisamente scomparire; dall’altro, il «costo» della rete non è spropositato, ossia il numero dei lati è relativamente «piccolo» rispetto al numero dei vertici (non si tratta dunque semplicemente di collegare tutti i vertici tra loro!). Più precisamente, a un grafo G si può associare una costante positiva h(G), detta costante di Cheeger di G (vedi FOCUS). Se h(G) > 0, il grafo è connesso: è sempre possibile collegare qualunque coppia di vertici seguendo i lati del grafo. Ma quanto maggiore è h(G), tanto più il grafo è «robusto»: per esempio, se h(G) vale almeno 1/10, si possono sempre collegare due parti del grafo di dimensioni simili, anche dopo averne rimosso un lato su dieci!

Avere grafi espansori significa quindi saper costruire, per ogni N arbitrariamente grande, un grafo con almeno N vertici, in cui ogni vertice è collegato al più a un «piccolo» numero fisso di altri vertici (per esempio, al più sei), e il cui numero di Cheeger è sempre almeno 1/10 (o qualunque altro valore fissato strettamente positivo).

Una storia movimentata ==================================================================================================

Per molto tempo la scoperta dei grafi espansori, e in particolare la dimostrazione dell’esistenza di questi oggetti, fu attribuita a Mark Semenovič Pinsker, nell’ambito di un problema di informatica teorica. Nel 1973 Pinsker introdusse infatti i grafi espansori come oggetti ausiliari che gli permettevano di portare a compimento una certa costruzione, e dimostrò che una successione di grafi sempre più grandi «scelta a caso», in cui ogni vertice ha sempre al più quattro vicini, è un espansore. Tuttavia, molto più recentemente Larry Guth (ri)scoprì un affascinante articolo di Yanis Barzdin e Andrej Kolmogorov, pubblicato nel 1967, alcuni anni prima di quello di Pinsker. Vi si trovano non solo una definizione essenzialmente equivalente a quella dei grafi espansori — con la differenza che Barzdin e Kolmogorov usano grafi orientati — e la dimostrazione della loro esistenza, ma anche la prima applicazione dei grafi espansori al di fuori della combinatoria e dell’informatica teorica. Questa applicazione è inoltre particolarmente elegante.

=

Le prime costruzioni =================================================================================================

La storia però continua. Infatti, tanto Barzdin e Kolmogorov quanto Pinsker dimostrano l’esistenza dei grafi espansori… senza fornirne esempi concreti. Affermano soltanto che, costruendo un grafo «senza pensarci», esso ha buone probabilità di essere espansore. Questo tipo di costruzione aleatoria, pur essendo perfettamente accettabile quando si tratta di dimostrare l’esistenza di certi oggetti, può porre due tipi di problemi.

Può già accadere che, per una certa applicazione concreta, non sia possibile scegliere da sé i grafi necessari. Sapere che esiste un grafo espansore serve a poco, se occorre verificare che un particolare grafo possieda buone proprietà di espansione.

Inoltre, è sempre naturale chiedersi se una costruzione aleatoria possa essere sostituita da una versione esplicita e deterministica.

Già nel 1973 Gregori Aleksandrovič Margulis riuscì a costruire esempi espliciti di grafi espansori. A tal fine utilizzò un argomento estremamente elegante, che collegava l’espansione di certi grafi a nozioni profonde di algebra e geometria. Da allora sono state scoperte molte altre costruzioni, ma l’esistenza dei grafi espansori conserva ancora un lato misterioso.

Una piccola questione di geometria ==========================================================================================================

Fra le numerose applicazioni dei grafi espansori, due fra le più belle sono direttamente legate all’articolo originario di Barzdin e Kolmogorov. La prima ne fu la motivazione, mentre la seconda, legata a un problema di teoria dei nodi, fu scoperta da Michail Gromov e Larry Guth.

Barzdin descrive così la motivazione nelle note alle opere di Kolmogorov:

Più precisamente, Barzdin e Kolmogorov considerano un grafo finito con N vertici, ciascuno dei quali ha, diciamo, al più sei vicini. Un tale grafo può sempre essere rappresentato nello spazio in modo che due lati non si intersechino, salvo eventualmente in un vertice comune. Se si suppone che vertici e lati siano rappresentati «fisicamente» da sfere o tubi di raggio 1 cm, la domanda diventa:

Qual è il più piccolo raggio R > 0 per cui si possa rappresentare il grafo nello spazio, all’interno di un cubo di lato R?

Barzdin e Kolmogorov ottengono due risultati:

– Si può sempre rappresentare un grafo in un cubo di lato circa N^1/2;

–Se il grafo è espansore (se la sua costante di Cheeger è «sufficientemente grande»), non lo si può rappresentare in un cubo di lato inferiore a circa N^1/2.

Barzdin e Kolmogorov dimostrano così, in un certo senso, che i grafi espansori sono «quanto più complessi possibile». La loro dimostrazione è relativamente elementare, purché si conosca la definizione esatta della costante di Cheeger (vedi FOCUS).

Il primo risultato di Barzdin e Kolmogorov era in realtà già noto ad alcuni informatici «applicati», per i quali è importante disporre di un algoritmo efficace per rappresentare fisicamente una rete in uno spazio tridimensionale.

Il secondo risultato, invece, non avrebbe alcun interesse se i grafi espansori non esistessero! Proprio per verificare che il loro enunciato non fosse vuoto, i due matematici russi dimostrarono poi l’esistenza di tali grafi. D’altra parte, è altrettanto chiaro che qui non è affatto necessario costruirne esplicitamente o disporre di esempi espliciti.

Il teorema di Gromov–Guth ====================================================================================================

La seconda applicazione dei grafi espansori è particolarmente elegante, anche perché l’enunciato del risultato finale non menziona affatto alcun grafo! Si tratta di una questione posta da Gromov negli anni Ottanta, riguardante un modo geometrico di misurare la complessità dei nodi. Poniamo un tale nodo nello spazio. Gromov definisce la distorsione del nodo come il massimo del rapporto A/B, dove A è la distanza fra due punti del nodo seguendo il nodo stesso, e B è la distanza «in linea d’aria» fra i due punti.

Ora spostiamo arbitrariamente il nodo nello spazio, permettendoci persino di stirarlo a piacere. A ogni posizione corrisponde una distorsione, e la distorsione intrinseca del nodo è la più piccola fra le distorsioni possibili quando il nodo assume tutte le posizioni possibili. Se un nodo ha una grande distorsione, significa che è straordinariamente complicato, poiché — comunque lo si presenti nello spazio — vi saranno punti «vicini» in linea d’aria che in realtà sono molto lontani lungo il nodo.

Come per i grafi espansori, l’esistenza di nodi tanto complicati non è affatto evidente. Gromov aveva infatti chiesto:

Esistono nodi di distorsione arbitrariamente grande?

Gromov e Guth, usando le proprietà di espansione di alcuni grafi particolari, riuscirono a rispondere affermativamente alla domanda.

Ci si può chiedere se, dato un grafo esplicito G, si possa calcolare rapidamente la sua costante di Cheeger h(G), verificando così se possieda buone proprietà di espansione. La definizione fornisce un metodo evidente per calcolare h(G), ma straordinariamente inefficace: così com’è, richiede un numero di operazioni pari a circa 2^N, dove N è il numero di vertici di G. Fortunatamente esiste un’altra costante associata al grafo, molto più facile da calcolare, che permette almeno di fornire stime della costante di Cheeger h(G). Restano però molte questioni aperte relative a questo campo in piena… espansione.