Grafi espansori – teoria delle reti | Tangente

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 anche 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 più ci interessano, i lati dei grafi considerati si considereranno non orientati.

Alcuni grafi particolari, detti espansori, possiedono proprietà così straordinarie che la loro stessa esistenza sembra paradossale. In effetti, più di un matematico sembra aver dapprima pensato che non potessero esistere! Inoltre, trovano applicazioni eccezionali in ambiti 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. Dimostra in modo spettacolare l’unità della matematica. Ancora oggi, in un’epoca in cui la ricerca è sempre più specializzata e spesso concettualmente difficile, possono nascere nuove idee rivoluzionarie, elementari e accessibili a un vasto pubblico.

Intuitivamente, un grafo espansore combina due proprietà che sembrano contraddittorie: da un lato, permette di collegare con grande efficienza due vertici qualsiasi, anche se molti suoi lati dovessero improvvisamente scomparire; dall’altro, il «costo» della rete non è spropositato, ossia il numero di lati è relativamente «piccolo» rispetto al numero di vertici (non basta dunque collegare semplicemente tutti i vertici tra loro!). Più precisamente, a un grafo G si può associare una costante positiva h(G), detta numero di Cheeger di G (vedi riquadro). Se h(G) > 0, il grafo è connesso: è sempre possibile collegare qualunque coppia di vertici seguendo i lati del grafo. Ma quanto più h(G) è grande, 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 aver eliminato un lato su dieci!

L’esistenza di grafi espansori significa dunque che si sanno costruire, per un numero N arbitrariamente grande, un grafo con almeno N vertici, nel quale ogni vertice è collegato ad al più un «piccolo» numero fisso di altri vertici (per esempio, ad al più sei altri vertici) e il cui numero di Cheeger vale sempre almeno 1/10 (o qualunque altro valore fisso strettamente positivo).

il numero di lati è molto superiore al numero di vertici.

basta un solo guasto per dividere la rete in due parti disconnesse.

Per molto tempo, la scoperta dei grafi espansori, e in particolare la dimostrazione dell’esistenza di questi oggetti, è stata 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 consentivano di portare a termine una certa costruzione, e dimostrò che una successione di grafi via via più grandi «scelti a caso», nella quale ogni vertice ha sempre al più quattro vicini, ha la proprietà di essere espansore. Tuttavia, molto più recentemente Larry Guth ha (ri)scoperto un affascinante articolo di Yanis Barzdin e Andrej Kolmogorov, pubblicato nel 1967, alcuni anni prima di quello di Pinsker. Vi si trova non solo una definizione sostanzialmente 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.

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

Può anzitutto accadere che, per una determinata applicazione concreta, non si sia liberi di scegliere i grafi necessari. Sapere che esiste un grafo espansore serve a poco se occorre verificare che un grafo particolare possieda buone proprietà di espansione.

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

Già nel 1973 Gregori Aleksandrovič Margulis riuscì a costruire esempi espliciti di grafi espansori. A questo scopo 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.

Tra le numerose applicazioni dei grafi espansori, due delle più belle sono direttamente legate all’articolo originale di Barzdin e Kolmogorov. La prima fu la loro motivazione; 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 il quale sia possibile rappresentare il grafo nello spazio, all’interno di un cubo di lato R?

Barzdin e Kolmogorov ottengono due risultati:

– Un grafo può sempre essere rappresentato in un cubo di lato circa N^1/2;

– Se il grafo è espansore (se la sua costante di Cheeger è «abbastanza 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 di più complesso possibile». La loro dimostrazione è relativamente elementare, una volta nota la definizione esatta della costante di Cheeger (vedi riquadro).

Il primo risultato di Barzdin e Kolmogorov era in realtà già noto ad alcuni informatici che si occupano di applicazioni, 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 è vuoto, i due matematici russi dimostrarono poi l’esistenza di tali grafi. È però altrettanto chiaro che qui non è affatto necessario costruire esplicitamente tali grafi né disporre di esempi espliciti.

Ogni vertice è collegato ad alcuni altri vertici scelti a caso.

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

Ora spostiamo il nodo arbitrariamente nello spazio, permettendoci persino di deformarlo a piacere. A ogni posizione corrisponde una distorsione, e la distorsione intrinseca del nodo è la minore tra tutte le distorsioni possibili quando gli si fanno assumere tutte le posizioni possibili. Se un nodo ha una grande distorsione, significa che è straordinariamente complicato, poiché — comunque lo si rappresenti 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 così complessi non è affatto evidente. Gromov pose infatti la domanda:

Esistono nodi di distorsione arbitrariamente grande?

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

Ci si può chiedere se, dato un grafo esplicito G, sia possibile calcolarne rapidamente la costante di Cheeger h(G) e verificare così se possieda buone proprietà di espansione. La definizione fornisce un metodo evidente per calcolare h(G), ma straordinariamente inefficiente: richiede infatti un numero di operazioni approssimativamente pari a 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 stimare la costante di Cheeger h(G). Restano tuttavia molte questioni aperte in questo campo in piena… espansione.