Punti e segmenti: avanti con la festa della matematica!

È difficile sapere quando la matematica vi prenderà. Tutto può cominciare molto semplicemente, per esempio dopo una lunga telefonata a un’amministrazione poco disponibile. Inconsapevolmente, prendete una penna mentre ascoltate ripetutamente un brano di Vivaldi e cominciate a scarabocchiare un disegno. Potreste ottenere, per esempio, il disegno qui accanto.

Avete collocato otto punti e tracciato otto segmenti fra tutti quelli che possono collegarli. La forma del «nove» sembra innocua, ma una particolarità vi colpisce: tutti i segmenti tracciati hanno la stessa lunghezza! Dopo aver riattaccato il telefono, completate avidamente il disegno aggiungendo altri due segmenti, sempre della stessa lunghezza, di cui uno nell’anello del «nove», e constatate che non potete aggiungerne altri senza introdurre nuovi punti.

Sorge spontanea una domanda matematica: fissato il numero n di punti, quanti segmenti della stessa lunghezza che colleghino questi n punti, disposti a piacere e con astuzia, si possono tracciare al massimo?

Per n = 3, il problema è facile: il triangolo equilatero fornisce una configurazione in cui tutti i segmenti tracciabili hanno la stessa lunghezza.

Per n = 4, il quadrato fornisce quattro segmenti della stessa lunghezza, i lati; ma si nota subito che si può fare meglio e ottenerne cinque affiancando due triangoli equilateri lungo uno dei loro lati. Un ragionamento geometrico permette poi di stabilire che non si possono avere sei segmenti della stessa lunghezza che colleghino quattro punti (ed è una piccola sfida lasciata all’acume dei lettori).

Tentativi con piccoli numeri di punti.

Per n = 5, si possono ottenere sette segmenti della stessa lunghezza aggiungendo un triangolo equilatero a uno dei lati esterni, ma non si può fare di meglio con un po’ più d’astuzia?

Mentre tentate di disegnare configurazioni con numeri di punti un po’ più grandi, riuscite a calcolare alcuni valori ottimali per piccoli valori di n. Vi chiedete che cosa accada quando n diventa davvero grande. In altre parole, a quale velocità evolve il numero massimo di segmenti della stessa lunghezza al variare del numero di punti? Così facendo, senza saperlo, riscoprite una congettura dell’illustre matematico ungherese Paul Erdős sulla stima asintotica di questa quantità!

Erdős aveva infatti annunciato in un brevissimo articolo del 1946 che «sembrava probabile» che il numero di segmenti fosse asintoticamente minore di n^a per ogni a > 1. Come d’abitudine, offriva perfino una ricompensa di cinquecento dollari a chiunque fosse in grado di dimostrare o confutare questa congettura! Segno che il risultato deve essere importante per i matematici, questo premio è fra i più generosi che avesse proposto.

Questa affermazione nata dall’intuizione di Erdős è ancora oggi una questione aperta. Il miglior risultato di cui disponiamo risale al… 1984: il numero massimo di segmenti è asintoticamente maggiorato da n^4/3. È un bel risultato ottenuto dai matematici Joel Spencer, Endre Szemerédi (peraltro premio Abel 2012) e William Trotter. La dimostrazione fu migliorata da Lazlo Székely nel 1997, ma teniamo bene a mente che restano molti possibili valori dell’esponente a fra 1 e 4/3. La congettura di Erdős resiste ancora…

Come spesso accade quando ci si interessa di questioni sui grafi, possiamo rivolgerci al grafo di Petersen. Lo si ricorda facilmente, tanto sembra nato da un rituale satanico. Più seriamente, si rivela un formidabile controesempio a molte intuizioni matematiche.

Il grafo di Petersen e il suo aspetto satanico.

Rispetto alla nostra questione, sembra invece assai deludente: i segmenti non hanno tutti la stessa lunghezza, anche se quelli del pentagono centrale ce l’hanno. Tuttavia, ruotando opportunamente i punti esterni e «stirando un po’» la figura, si riesce a rendere tutti i segmenti della stessa lunghezza! Si modifica il disegno, ma si conservano i segmenti che collegavano i punti: questi restano «attaccati», «collegati» quando i punti si muovono. Si ottiene così un’altra rappresentazione del grafo di Petersen, che questa volta gode della proprietà cercata.

Un’altra rappresentazione del grafo di Petersen. Questa volta tutti i segmenti hanno la stessa lunghezza.

In termini tecnici, si chiama grafo a distanza unitaria un grafo che ammette un disegno in cui tutti i segmenti hanno la stessa lunghezza. Ecco una seconda domanda matematica apparentemente innocua: tutti i grafi sono a distanza unitaria? In altre parole, per ogni disegno di un grafo, esiste uno spostamento dei punti che renda tutti i segmenti tracciati della stessa lunghezza? La risposta è negativa, e lo sapete già se avete affrontato la piccola sfida iniziale. Infatti, con quattro punti si possono realizzare al massimo cinque segmenti della stessa lunghezza; di conseguenza, prendendo quattro punti e collegandoli con sei segmenti, cioè tracciando tutti i segmenti possibili, si ottiene un grafo che, anche dopo aver spostato i punti, avrà sempre due segmenti di lunghezze diverse.

Modifichiamo allora la domanda: come riconoscere i grafi a distanza unitaria? Il problema è piuttosto difficile, anzi molto difficile. Per convincervene, osservate questo grafo molto particolare, detto grafo di Heawood.

Il grafo di Heawood con i suoi quattordici punti e ventuno segmenti.

In questo schema, non tutti i segmenti hanno la stessa lunghezza. È una proprietà facile da verificare. Al contrario, ci vorrà molta astuzia per dire se esiste una rappresentazione del grafo di Heawood in cui tutti i segmenti hanno la stessa lunghezza! Trovare una rappresentazione adatta è difficile, ma verificare che una rappresentazione sia adatta è facile. Nel 2013 il matematico tedesco Marcus Schaefer stabilì che questo problema era NP-completo, cioè, grosso modo, che appartiene alla classe dei problemi equivalenti considerati molto difficili da risolvere, ma per i quali esistono semplici verifiche delle soluzioni.

Detto questo, si può dimostrare che il grafo di Heawood è effettivamente un grafo a distanza unitaria.

Dall’esempio di quattro punti nel piano si può anche capire come individuare i grafi che non sono a distanza unitaria. È impossibile costruire un disegno in cui i sei segmenti abbiano la stessa lunghezza; non è del tutto vero, o meglio, lo è nel piano. Se questa volta realizziamo un disegno in tre dimensioni, è invece facile costruire un tetraedro regolare i cui lati hanno tutti la stessa lunghezza!

Per un grafo qualsiasi, tre dimensioni non bastano sempre e si introduce la nozione di dimensione minima dello spazio nel quale il grafo ammette una rappresentazione in cui tutti i segmenti hanno la stessa lunghezza (vedi il riquadro). Eravamo partiti da un disegno scarabocchiato durante un’attesa telefonica ed eccoci proiettati nella quarta dimensione o oltre! Davvero, non si sa mai quando la matematica ci prenderà…