Ramsey

[Roberto Zanasi]

Dato che ormai sono scaduti i termini per proporre soluzioni al numero
di settembre di RM, riporto un messaggio che scrissi un po' di giorni
fa a Piotr. Riguarda la soluzione del problema delle città della
Catalogna, di cui mi piacerebbe discutere.

====
Abbiamo un grafo completo di ordine N (cioè un poligono di N lati con
tutte le possibili diagonali). Vogliamo colorarle con tre colori in
modo tale che non vi siano triangoli coi lati tutti dello stesso
colore. Questo si chiama problema di Ramsey multicolore

http://en.wikipedia.org/wiki/Ramsey%27s_theorem

(il problema originale, o più famoso, era bicolore, noto anche come il
problema delle strette di mano).

Ho scritto un programma che sfrutta il backtracking per trovare una
soluzione a questo problema, per N via via crescente - il programma è
scritto in python (lo so, non brilla per velocità) e lo allego qua
sotto.

Si dimostra "facilmente" (il punto è proprio qui) che si riesce a
colorare al massimo un grafo di ordine 16. Ora, dimostrare che un
grafo di ordine 17 è impossibile da colorare è semplice, vedi la
pagina di wikipedia. Dimostrare invece che un grafo di ordine 16 è
colorabile è difficile (cioè, nella pagina di wikipedia ci sono due
disegnini: sono due modi per farlo, e pare che siano unici, e quindi
la dimostrazione è già lì, ma io vorrei ripercorrere la strada;
insomma, faccio finta che quei due grafici non esistano e voglio
trovarli).

Domanda: come faccio a trovarli? Il programma ha questi tempi di esecuzione:

N=7: 0m0.116s
N=8: 0m3.082s
N=9: 3m35.373s

L'esplosione combinatoria è evidente: io dovrei arrivare a N=16. Il
fatto è che in giro si trovano valori anche per problemi molto più
difficili di questo, quindi in un qualche modo ci si deve riuscire.
Certamente non si può esplorare l'intero spazio delle configurazioni
(3^120 possibilità, a meno di simmetrie non calcolate), e il problema
è NP, quindi non ci sono trucchetti.

Immagino che, scrivendo il programma in C, potrei fare qualche passo
avanti, ma dubito di arrivare fino a N=16.

Stavo pensando di domandare alla mailing list dei Rudi Mathematici: da
un po' langue e magari questo problema potrebbe interessare. Ho letto
che in giro si parla anche di algoritmi genetici, ma non capisco bene
cosa posso fare evolvere qua. In che modo posso assegnare un peso a
configurazioni parziali "buone"?

Vabbè, questa non è una soluzione ma sono domande. Comunque sia,
questo è il programma:

N = 9

grafo=[[a,b] for a in xrange(N) for b in xrange(a+1,N)]

print grafo

lunghezza=len(grafo)
print "Numero archi: ",lunghezza

def formatriangolo(arco,colore):
papabili=[a for a in archi[colore] if len(set(a) & set(arco))!=0]
lun=len(papabili)
for i in xrange(lun):
for j in xrange(i+1,lun):
for k in xrange(j+1,lun):
if len(set(papabili[i])|set(papabili[j])|set(papabili[k]))==3:
return True
return False

archi=[[],[],[],[]]

def colora(n,colore):
if n>=lunghezza:
return True
arco=grafo[n]
archi[colore]+=[arco]

if not formatriangolo(arco,colore):
#bene, possiamo andare avanti

if colora(n+1,1):
return True
elif colora(n+1,2):
return True
elif colora(n+1,3):
return True
else:
#le ho provate tutte, i colori non vanno bene, torno indietro
archi[colore].remove(arco)
return False
else:
#la scelta del colore non va bene
archi[colore].remove(arco)
return False
return True

colora(0,1)

print archi[1]
print archi[2]
print archi[3]

Ciao
====

Ecco qua, dato che il numero di ottobre non è ancora uscito, non so se
qualcuno ha risolto il problema nel modo in cui vorrei farlo io. Se
qualcuno ha voglia di pensarci...

Ciao

[fabrizio bertuccelli]

Salve a tutti,

di recente, più per caso che per altro, mi sono imbattuto in una dimostrazione 

del fatto che  K16 è 3-colorabile (vedi "A new construction technique of a

triangle-free 3-colored K16's" Jihad Mohamad Jaam Information Sciences 177

(2007) pagg. 1992-1995).

Mi sono allora ricordato del post di Roberto e sperando di fare cosa gradita

ho tradotto (liberamente) la dimostrazione in questione (vedi pdf allegato,

se vi trovate qualche errore abbiate pietà e segnalatemelo pure).

Ora in realtà mi sembra che Roberto fosse interessato ad un algoritmo da

eseguire su un computer che fosse in grado di determinare

le due colorazioni buone; qui invece una delle due colorazioni buone (credo

non ho verificato che sia effettivamente così ma se è vero che ve ne sono solo due..)

è ottenuta tramite una costruzione basata sulla ripartizione dell'insieme K16 in

sottoinsiemi privi di triangoli monocromatici.

Non risolve dunque completamente il problema posto da Roberto ne fornisce una

prova che le colorazioni buone di K16 sono solo due e nemmeno dà un'indicazione

di come trovare l'altra; tuttavia è pur sempre meglio questo della scarso accenno 

di Wikipedia.

In realtà per questo bisognerebbe riuscire a trovare l'articolo "Combinatorial relations 

and chromatic graphs" di R.E. GreenWood e A.M. Gleason su Canadian Journal of

Mathematics 7 (1995) pagg. 1-7 ma in rete risulta accessibile solo dietro pagamento.

Altro articolo interessante potrebbe essere "Etude de Symetries et de la Cardinalitè en Calcul

Propositionnel Application aux Algorithmes Syntaxiques" di B. Behamou del 1993 ma anche

di questo non sono riuscito a trovare una versione elettronica in rete. 

Magari qualcuno potrebbe partire dal teorema allegato per riuscire a risolvere la questione.

Comunque dal canto mio sto provando anche a generare qualche algoritmo buono

per il computer. Spero di poter postare presto qualche cosa (ahiahia quando dico così

poi finisce che non posto niente).

Infine l'augurio è che non CiVuDi non sia finito e che vi sia ancora qualcuno che abbia voglia 

di dire la sua dalle pagine di questo sito.

A presto,

                 Fabrizio

  

 

 

 

 

 

[Roberto Zanasi]

2010/5/5 fabrizio bertuccelli <fabrizio.b...@gmail.com>:

> Mi sono allora ricordato del post di Roberto e sperando di fare cosa gradita
> ho tradotto (liberamente) la dimostrazione in questione (

Uelà, grazie.

[gn...@libero.it]

Incredibile! C'è vita su Marte.
Per la serie a volte un disegno è meglio di un discorso, allego (tento di
allegare) grafici dei servizi di trasporto in Catalogna.
Credo che saremmo in grado di dimostrare che con 4 colori sia impossibile un
grafo completo con 65 vertici privo di triangoli monocromatici e così via.
Ciao a tutti

>----Messaggio originale----
>Da: gn...@libero.it
>Data: 07/05/2010 6.48
>A: <gn...@libero.it>
>Ogg: Fwd: Ramsey
>
>
>
>
>---------- Forwarded message ----------
>From: Roberto Zanasi <roberto.zan...@gmail.com>
>Date: 5 Mag, 20:04
>Subject: Ramsey
>To: CiVuDi
>
>
>2010/5/5 fabrizio bertuccelli <fabrizio.bertucce...@gmail.com>: