Apr 25

Una semplice applicazione del teorema di Ramsey: il Party Problem **

Esponiamo come promesso, una semplice  applicazione del teorema di Ramsey. Il nostro scopo è tradurre un problema pratico nella linguaggio dei grafi e delle colorazioni.

  1. Il party Problem:

Supponiamo di organizzare una festa, con n persone scelte a caso e chiediamoci quando  sia verificata o meno la seguente condizione:

  1. Vi è almeno una terna di persone che mutuamente si conoscono oppure una terna di persone che mutuamente non si conoscono. 

Possiamo tradurre il problema nel linguaggio dei grafi.  Le persone presenti costituiscono i vertici del grafo.La condizione richiesta si basa evidentemente su una variabile booleana, ovvero ha solo due valori; vero o falso, ovvero rosso o blu. Tutti gli elementi possono essere messi in relazione fra di essi; se vale la proprietà "si conoscono" possiamo ad esempio  parlare di colore blu, altrimenti , se non si conoscono parliamo di colore rosso. Il grafo è quindi un grafo completo (se pensiamo alla relazione come ad un lato che congiunge due vertici rappresentanti le persone, esse o si conoscono o non si conoscono e il lato assume due diversi colori).

La questione quindi si traduce in tal modo, per poter applicare il teorema si Ramsey: data una colorazione dei lati di un grafo completo Kn mediante due colori, qual è il valore minimo di n affinchè il grafo contenga un sottografo completo K3 (triangolo) che sia monocromatico? La condizione espressa sopra è che se n è maggiore o uguale a 6 allora c'è sicuramente un triangolo monocromatico. Questo è proprio il teorema di Ramsey;(lo abbiamo  risolto in particolare in questo quiz, in modo autonomo)

Quindi, se facciamo una festa e invitiamo un certo numero di persone qualsiasi, il teorema di Ramsey ci assicura che se n è maggiore o uguale a sei, allora la condizione 1) è sempre verificata.

Chiaramente possiamo estendere il problema , da tre persone o quattro o più che si conoscono o non si conoscono; chiamiamo m tale numero.Data una colorazione dei lati di un grafo completo Kn mediante due colori, qual è il valore minimo di n affinchè il grafo contenga un sottografo completo Km che sia monocromatico? Sappiamo, dal teorema di Ramsey, che tale numero esiste (nel senso  che non è infinito), ma non sempre sappiamo dire quale sia.

Questo è un semplice esempio; molte sono le applicazioni del teorema di Ramsey alla geometria, all'informatica e agli insiemi. Ma aspettiamo di vedere il teorema di Ramsey nel caso infinito, per poter dire qualcosa in più. Sarà l'obiettivo del prossimo articolo.

 

Lascia un commento

*

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)

 

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.