Don't take life too seriously: it's just a temporary situation

Zarankiewicz (congettura di)

Congetture  Matematica combinatoria  Teoria dei grafi 

La congettura di Zarankiewicz afferma che se si disegna sul piano un grafo bipartito con m nodi in un insieme e n nell’altro, con ogni nodo di un insieme connesso a tutti i nodi dell’altro, il numero minimo di incroci tra gli archi è Numero minimo di incroci tra gli archi.

 

Nel 1954 Kazimiercz Zarankiewicz (2/5/1902 – 5/9/1959) e indipendentemente K. Urbaník nel 1955 proposero una dimostrazione della congettura, ma Paul Kainen nel 1965 e indipendentemente Gerhard Ringel nel 1966 trovarono un errore nelle dimostrazioni, che nessuno fu in grado di correggere.

La dimostrazione che il numero di incroci indicato dalla formula è sufficiente resta valida ed è semplice: si dispongono i nodi di un insieme lungo l’asse x, uniformemente spaziati, divisi quanto più equamente possibile tra la parte positiva e quella negativa, poi si fa lo stesso con i nodi dell’altro insieme lungo l’asse y e si collega ogni nodo di un insieme a tutti quelli dell’altro, ottenendo un diagramma come quello mostato nella figura seguente.

 

Diagramma per il numero minimo di incroci tra gli archi

 

A questo punto è facile verificare che la formula indica il numero di incroci; la parte difficile è dimostrare che non sia possibile ridurre gli incroci disponendo i punti in modo diverso e utilizzando collegamenti non rettilinei.

 

La dimostrazione di Zarankiewicz era comunque valida per m = 3 e qualsiasi valore di n; in seguito vi furono pochi progressi nell’estenderla a grafi con più nodi: nel 1970 Daniel J. Kleitman dimostrò che la congettura vale per m fino a 6 e qualsiasi n; Douglas R Woodall nel 1993 dimostrò con l’aiuto di un calcolatore che vale per m fino a 8 e n fino a 10. Quindi i minimi casi irrisolti sono n = 7, m = 11 e n = m = 9.

 

Robin Christian, R. Bruce Richter e Gelasio Salazar dimostrarono che esiste un valore Formula per N(m) tale che se la congettura vale per m fissato e n fino a N(m), allora per quel valore di m vale per qualsiasi valore di n. Sfortunatamente N(m) cresce tanto velocemente da rendere il teorema di nessuna utilità pratica anche per m piccolo, però se si riuscisse a ridurre tale valore, si potrebbe arrivare alla dimostrazione della congettura per qualche altro valore di m.

Vedi anche

Numero di incroci.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.